Namespaces
Variants
Actions

Turán number

From Encyclopedia of Mathematics
Jump to: navigation, search

A collection 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
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