Namespaces
Variants
Actions

Difference between revisions of "Turán number"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (moved Turan number to Turán number over redirect: accented title)
m (AUTOMATIC EDIT (latexlist): Replaced 23 formulas out of 23 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
A collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201901.png" /> of subsets of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201902.png" /> ( "blocks" ) of a ground set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201903.png" /> of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201904.png" /> is said to form a Turán <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201906.png" />-system if each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201907.png" />-element subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201908.png" /> contains at least one block. The Turán number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t1201909.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019010.png" />, defined to be the smallest number of blocks needed to cover (by inclusion) each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019011.png" />-element subset. Several recursions are known; e.g. in [[#References|[a2]]] it is shown that
+
<!--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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019012.png" /></td> </tr></table>
+
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
 
Also, the limit
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019013.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019014.png" /> are known only for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019015.png" />. These facts and the ones that follow are based on an extensive survey by A. Sidorenko ([[#References|[a5]]]):
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019016.png" />.
+
i) $t ( k , r ) \leq t ( k - 1 , r - 1 )$.
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019017.png" /> [[#References|[a1]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019018.png" /> [[#References|[a1]]].
+
iii) It has been conjectured that $\operatorname { lim } _ { r \rightarrow \infty } r \cdot t ( r + 1 , r ) = \infty$ [[#References|[a1]]].
  
iv) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019019.png" /> [[#References|[a4]]].
+
iv) $t ( r + 1 , r ) \leq \frac { \operatorname { ln } r } { 2 r } ( 1 + o( 1 ) )$ [[#References|[a4]]].
  
v) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019020.png" /> [[#References|[a3]]]. The situation of small <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019021.png" /> has been studied extensively, as have been the cases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019022.png" />. The case of small <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019023.png" /> is also well-studied; this leads to the covering number. See [[#References|[a5]]] for details.
+
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====
 
====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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120190/t12019024.png" />-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>
+
<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>

Latest revision as of 16:57, 1 July 2020

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