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.

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

2 Answers 2

Reset to default
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].

Improve this answer
$\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$.

Improve this answer
$\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$
    – Włodzimierz Holsztyński
    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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .