Minimal family of k-sets containing all t-sets Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member of $\mathcal{F}$. My question is: How small can $\mathcal{F}$ be? In other words, what is the smallest possible size of $\mathcal{F}$, in terms of $n,k,t$? Is it a known theorem?
Obviously, if $k=n$ then $|\mathcal{F}|=1$. It is also not hard to see that if $k=n-1$, then the smallest possible size of $|\mathcal{F}|$ is $t+1$.
 A: I think it is an optimal version of a covering with index $1$.
A $t$-$(n,k,\lambda)$ covering is an ordered pair $(U,\mathcal{B})$ of a finite set $U$ of cardinality $n$ and a finite set $\mathcal{B}$ of $k$-subsets of $U$ such that every $t$-subset appears as a subset in at least $\lambda$ elements of $\mathcal{B}$. So, your $\mathcal{F}$ is the $\mathcal{B}$ of a covering with $\lambda = 1$.
The size of a smallest $t$-$(n,k,\lambda)$ covering for given $t$, $n$, $k$, and $\lambda$ (or, more precisely, the smallest realizable $\mathcal{B}$ for given parameters) is called the covering number $C_\lambda(n,k,t)$. So, what you want to know is exactly the covering number.
It is not difficult to see that $C_\lambda(n,k,t) \geq \frac{nC_\lambda(n-1,k-1,t-1)}{k}$. So, repeating this process, we get a lower bound
$$C_\lambda(n,k,t) \geq \left\lceil\frac{n}{k}\left\lceil\frac{n-1}{k-1}\dots\left\lceil\frac{\lambda(n-t+1)}{k-t+1}\right\rceil\right\rceil\right\rceil.$$
This is known as the Schönheim bound.
There are results in design theory on $C_\lambda(n,k,t)$, and most of the major results should be listed or referenced in Section 11 of the 2nd edition of the Handbook of Combinatorial Designs. The above lower bound should be noted there as well. Determining the exact value of $C_\lambda(n,k,t)$ in general seems very difficult. So, I think it's still an open problem, though there are cases the exact covering number is known.
There is also an online database known as La Jolla Covering Repository. If you're only interested in specific cases, looking up the online tables may be more helpful than reading up on coverings in the literature.
