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!

Improve this question
$\endgroup$
4

3 Answers 3

Reset to default
5
$\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.

Improve this answer
$\endgroup$
1
  • 5
    $\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, 2017 at 12:08
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$.

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

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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