8
$\begingroup$

Let $d , n$ be positive integers such that $d < n/2$. Consider collections $\mathcal{F}$ consisting of subsets of $[n] = \{1,2,\ldots, n\}$ of size $n/2$. Question: what is the minimal size of a collection $\mathcal{F}$, such that every size-$d$ subset of $[n]$ is contained in \textit{at least} one set in $\mathcal{F}$ ?

I did searches in literature and if the "at least" above is changed to "exactly one" then it is called Steiner designs and is considered a hard problem. Just wondering if the above version is easier...

I had some initial idea but got stuck on how to make it work: say $n = 2^k$, then we can regard $[n]$ as $\mathbb{F}_2^k$, and select all hyperplanes. But I don't know if such collection satisfies the condition ... any ideas are appreciated!

$\endgroup$
5
$\begingroup$

Choose $N$ $n/2$-sets at random (repetitions allowed). The probability that a given $d$-set $T$ is not covered by them equals $$p=\left(1-\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right)^N\leqslant \exp\left(-N\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right).$$ If $p<1/\binom{n}d$, with positive probability each $d$-set is covered by one of $n/2$-sets. So, if $$N>\frac{\binom{n}{n/2}}{\binom{n-d}{n/2-d}}\log\binom{n}d=\frac{\binom{n}{d}}{\binom{n/2}{d}}\log\binom{n}d,$$ with positive probability we get the desired property of our collection. This is worse than Dustin G. Mixon's lower bound by a multiple $\log\binom{n}d$.

$\endgroup$
  • $\begingroup$ Eliminating this log factor may however be very difficult. See my comments to the OP above. $\endgroup$ – Sam Hopkins Nov 1 '17 at 14:15
4
$\begingroup$

By counting, you need at least $\binom{n}{d}/\binom{n/2}{d}$ different $n/2$-subsets. By the main estimate in this blog post, this is at least $\frac{1}{4}\cdot2^d$ when $d\leq\sqrt{n/2}$.

In the special case where $d$ divides $n/2$, it suffices to have $\binom{2d}{d}\leq 4^d$ different $n/2$-subsets. To see this, partition $[n]$ into subsets $S_1,\ldots,S_{2d}$ of equal size. Then every $d$-subset of $[n]$ is contained in the union of some $d$ of these $S_i$'s.

$\endgroup$
  • 4
    $\begingroup$ It is at least $2^d$ always by obvious reasons: $\binom{n}d/\binom{n/2}d=\prod_{i=0}^{d-1}\frac{n-i}{n/2-i}\geqslant 2^d$. $\endgroup$ – Fedor Petrov Nov 1 '17 at 12:08
4
$\begingroup$

These are called covering designs. See https://www.ccrwest.org/cover.html for references and tables of known values and bounds.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.