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

How to Cite This Entry:
Turán number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tur%C3%A1n_number&oldid=50207
This article was adapted from an original article by A.P. Godbole (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article