Choosing subsets to cover larger sets

Question

I think this is probably known/easy, but I can't solve it.

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ contains at least one of the chosen subsets.

Clearly $f(a,b)\leq \dbinom{n}{a}$, the number of subsets of $S$ of size $a$. (Choosing all subsets certainly satisfies the condition.)

Edit: Please see here for further discussion.

Answer 1

Revised: We can at least get a somewhat better upper bound.

Suppose that $B\subseteq S$ with $|B|=b$. For $k=0,\ldots,a-1$ there are $\binom{b}k\binom{n-b}{a-k}$ subsets $A$ of $S$ such that $|A|=a$ and $A\nsubseteq B$, so there is a family of

$$\sum_{k=0}^{a-1}\binom{b}k\binom{n-b}{a-k}$$

subsets of $S$ of cardinality $a$, none of which is a subset of $B$. Every other $a$-subset of $S$ is a subset of $B$. Thus,

$$f(a,b)\le 1+\sum_{k=0}^{a-1}\binom{b}k\binom{n-b}{a-k}\;.$$

Note that $\binom{b}k\binom{n-b}{a-k}=0$ if $k<0$ or $k>a$, so

$$\begin{align*} \sum_{k=0}^{a-1}\binom{b}k\binom{n-b}{a-k}&=\sum_k\binom{n}k\binom{n-b}{a-k}-\binom{b}a\binom{n-b}0\\ &=\binom{n}a-\binom{b}a \end{align*}$$

by Vandermonde’s identity. Finally, then,

$$f(a,b)\le\binom{n}a-\binom{b}a+1\;.$$

Added₁: Of course, I did this the hard way: $S$ has $\binom{n}a$ subsets of cardinality $a$, $\binom{b}a$ of which are subsets of $B$, so it has $\binom{n}a-\binom{b}a$ that are not subsets of $B$.

Added₂: This upper bound is definitely not $f$, however. Take $n=5,a=2$, and $b=3$, and consider the family

$$\left\{\{1,2\},\{3,4\},\{1,5\},\{2,5\}\right\}$$

of two-element subsets of $S=\{1,2,3,4,5\}$. If $B$ is a three-element subset of $S$ that contains neither $\{1,2\}$ nor $\{3,4\}$, then $5\in B$, and since $\{3,4\}\nsubseteq B$, it’s clear that $B\cap\{1,2\}\ne\varnothing$ and hence that $B$ contains either $\{1,5\}$ or $\{2,5\}$. Thus, for $n=5$ we have $f(2,3)\le 4$. In fact $f(2,3)=4$. If we $\mathscr{A}$ is a collection of two-element subsets such that every three-element subset of $S$ contains a member of $\mathscr{A}$, we may assume that $\{1,2\}\in\mathscr{A}$. Now let $B$ be a three-element subset of $S$ such that $B\cap\{1,2\}=\{1\}$; if $B$ is to contain a member of $\mathscr{A}$, we must have $B\setminus\{1\}\in\mathscr{A}$. But there are $\binom32=3$ possibilities for $B\setminus\{1\}$, so $|\mathscr{A}|\ge 4$.

Answer 2

Let $B$ be our subset of size $b$, and let $A$ have size $a$. We can instead find the maximum number of subsets $A$ that aren't contained in $B$, and then to find the number stated in the problem, just add $1$.

There are $n-b$ elements outside $B$. (Let's say WLOG that $\{1,2,\dots,n-b \}$ are outside $B$). We require $A$ contain at least one of them. The remaining $a-1$ elements in $A$ can be anything.

Looking at the sets $A$ containing $1$, there are $\dbinom{n-1}{a-1}$ of them.

Looking at the sets containing $2$ and excluding the ones that contain $1$ because we've already counted them, there are $\dbinom{n-2}{a-1}$ of them.

So we can write the total as:

$$\sum_{i=1}^{n-b} \dbinom{n-i}{a-1}$$

And there's probably some nice formula out there to simplify this.