# Choosing subsets to cover larger sets

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?

It is not hard to obtain a bound $f(a,b)\leq \dbinom{n}{a}-\dbinom{b}{a}+1$, as is shown here. But it doesn't seem easy to go beyond that. However, since this is such a simply-stated question, I would expect that it has been well-studied in combinatorial set theory. So, any references to better upper or lower bounds (or better yet, the exact answer) would be appreciated.

• If you can, have a look at: Ian Anderson, Combinatorics of Finite Sets, ISBN 0-486-42257-7. – Włodzimierz Holsztyński Oct 12 '14 at 2:06
• Also take complements, and look at La Jolla covering repository. – The Masked Avenger Oct 12 '14 at 3:10

This is Turán's problem. I quote the opening paragraph of A. E. Brouwer and M. Voorhoeve, "Turán theory and the lotto problem", Mathematical Center Tracts 106 (1979), 99-105 = Chapter 7 of A. Schrijver, ed., Packing and Covering in Combinatorics, Mathematisch Centrum, Amsterdam, 1979, ISBN 90-6196-180-7.

Let $k,\ell,n\in\mathbb N$ such that $k\le\ell\le n$. We define the Turán number $T(n,k,\ell)$ as the smallest number of $k$-subsets of an $n$-set $X$ such that any $\ell$-subset of $X$ contains at least one of these $k$-subsets. For example: $T(7,4,5)=7$. (Take $X=\{0,1,\dots,6\}$; the $4$-subsets are all translates $\pmod7$ of $\{1,2,3,5\}$; this is easily seen to be optimal.) The relation between Turán numbers and covering numbers is discussed in Chapters 4 and 5. The above definition can be formulated in the language of hypergraphs (see Chapter 1) as follows: for a hypergraph $H=(X,\mathcal E)$, let its stability number $\beta(H)$ be the maximal cardinality of a stable subset of $H$ (i.e. a set containing no edge). Then $T(n,k,\ell)$ is the minimal number of edges of a $k$-uniform hypergraph $H$ with $n$ vertices such that $\beta(H)\lt\ell$.
P. TURÁN [10] posed the problem of determining $T(n,k,\ell)$. In this section we give some estimates for this number. Notice that $T(n,k,\ell)$ is increasing in $n$ and $k$ and decreasing in $\ell$. Trivially, $T(n,1,\ell)=n-\ell+1$. The numbers $T(n,2,\ell)$ and the corresponding graphs are determined by the following theorem of TURÁN [9].

For starters, let's have the upper bound for $\ f(2\ 3);\$ then it will be easy to generalize this approach. Partition $\ S\$ into two sets $\ S=X\cup Y\$ of cardinalities $\ \lfloor\frac n2\rfloor\$ and $\ \lceil\frac n2\rceil.\$ Let $\ A\$ be the family of all $2$-subsets $\ \alpha\subseteq S\$ such that $\ \alpha\subseteq X$ or $\ \alpha\subseteq Y.\$ Then every 3-subset of $\ S\$ contains a member of $\ A.\$ This proves that:

$$f(2\ 3)\ \le\ \binom{\lfloor\frac n2\rfloor}2 + \binom{\lceil\frac n2\rceil}2$$

(I'll clean it up later :-). Clearly, this is a clear improvement over @boaten's $\ \binom n2 - 2$.

• The case $a=2$ is completely answered by Turán's theorem. (Of course, finding the maximum number of edges in a subgraph of $K_n$ containing no $K_b$ is equivalent to finding the minimum number of edges in a subgraph of $K_n$ containing at least one edge of each $K_b$-subgraph of $K_n$.) – bof Oct 12 '14 at 3:18
• Right, this situation felt instantly familiar. (I'd written in the past a manuscript in which I generalized quite a bit Turán's theorem but it's gone, oh well). – Włodzimierz Holsztyński Oct 12 '14 at 3:26
• E.g., by Turán's theorem, $$f(2,3,n)=\binom n2-\lfloor\frac{n^2}4\rfloor=\binom{\lfloor\frac n2\rfloor}2+\binom{\lceil\frac n2\rceil}2$$ – bof Oct 12 '14 at 3:28