View source for Turán number

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 23 formulas, 23 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
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 [[#References|[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 [[#References|[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 ([[#References|[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)$ [[#References|[a1]]].

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

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

v) $t ( k , r ) \leq \left( \frac { r - 1 } { k - 1 } \right) ^ { r - 1 }$ [[#References|[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 [[#References|[a5]]] for details.

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