Turán number

A collection $\mathcal{B}$ of subsets of size $r$ ( "blocks" ) of a ground set $\mathcal{X}$ of size $n$ is said to form a Turán $( n , k , r )$-system if each $k$-element subset of $\mathcal{X}$ contains at least one block. The Turán number $T ( n , k , r )$ is the minimum size of such a collection. P. Turán introduced these numbers in [a6]. The related dual notion is that of the covering number $C ( n , k , r )$, defined to be the smallest number of blocks needed to cover (by inclusion) each $k$-element subset. Several recursions are known; e.g. in [a2] it is shown that

$$\begin{equation*} T ( n , k , r ) \geq \lceil \frac { n } { n - r } T ( n - 1 , k , r ) \rceil. \end{equation*}$$

Also, the limit

$$\begin{equation*} t ( k , r ) = \operatorname { lim } _ { n \rightarrow \infty } \frac { T ( n , k , r ) } { \left( \begin{array} { l } { n } \\ { r } \end{array} \right) } \end{equation*}$$

is known to exist, though the values of $t ( k , r )$ are known only for $r = 2$. These facts and the ones that follow are based on an extensive survey by A. Sidorenko ([a5]):

i) $t ( k , r ) \leq t ( k - 1 , r - 1 )$.

ii) $T ( n , k , r ) \geq \frac { n - k + 1 } { n - r + 1 } \left( \begin{array} { c } { n } \\ { r } \end{array} \right) / \left( \begin{array} { c } { k - 1 } \\ { r - 1 } \end{array} \right)$ [a1].

iii) It has been conjectured that $\operatorname { lim } _ { r \rightarrow \infty } r \cdot t ( r + 1 , r ) = \infty$ [a1].

iv) $t ( r + 1 , r ) \leq \frac { \operatorname { ln } r } { 2 r } ( 1 + o( 1 ) )$ [a4].

v) $t ( k , r ) \leq \left( \frac { r - 1 } { k - 1 } \right) ^ { r - 1 }$ [a3]. The situation of small $n/ ( k - 1 )$ has been studied extensively, as have been the cases $r = 2,3,4$. The case of small $n - k$ is also well-studied; this leads to the covering number. See [a5] for details.

References

[a1]	D. de Caen, "Extension of a theorem of Moon and Moser on complete subgraphs" Ars Combinatoria , 16 (1983) pp. 5–10
[a2]	G. Katona, T. Nemetz, M. Simonovits, "On a graph problem of Turán" Mat. Lapok , 15 (1964) pp. 228–238
[a3]	A. Sidorenko, "Systems of sets that have the $T$-property" Moscow Univ. Math. Bull. , 36 (1981) pp. 22–26
[a4]	A. Sidorenko, "Upper bounds on Turán numbers" J. Combin. Th. A , 77 : 1 (1997) pp. 134–147
[a5]	A. Sidorenko, "What we know and what we do not know about Turán numbers" Graphs Combin. , 11 (1995) pp. 179–199
[a6]	P. Turán, "Research Problems" Magyar Tud. Akad. Mat. Kutato Internat. Közl. , 6 (1961) pp. 417–423