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.

  • $\begingroup$ If you can, have a look at: Ian Anderson, Combinatorics of Finite Sets, ISBN 0-486-42257-7. $\endgroup$ – Włodzimierz Holsztyński Oct 12 '14 at 2:06
  • $\begingroup$ Also take complements, and look at La Jolla covering repository. $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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$.) $\endgroup$ – bof Oct 12 '14 at 3:18
  • $\begingroup$ 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). $\endgroup$ – Włodzimierz Holsztyński Oct 12 '14 at 3:26
  • 1
    $\begingroup$ 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$$ $\endgroup$ – bof Oct 12 '14 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.