Skip to main content
4 of 4
deleted 313 characters in body
Or Meir
  • 419
  • 2
  • 8

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

Or Meir
  • 419
  • 2
  • 8