3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If you can, have a look at: Ian Anderson, Combinatorics of Finite Sets, ISBN 0-486-42257-7. $\endgroup$ Commented Oct 12, 2014 at 2:06
  • $\begingroup$ Also take complements, and look at La Jolla covering repository. $\endgroup$ Commented Oct 12, 2014 at 3:10

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
1
$\begingroup$

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

$\endgroup$
3
  • 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
    Commented Oct 12, 2014 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$ Commented Oct 12, 2014 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
    Commented Oct 12, 2014 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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