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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .