Minimal number of n/2-subsets of [n] that contains every d-subset 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!
 A: 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.
A: 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$.
A: These are called covering designs. See https://www.ccrwest.org/cover.html for references and tables of known values and bounds.
