View source for Turán number

In mathematics, the '''  Turán number''' T(''n'',''k'',''r'') for  ''r''-uniform [[hypergraph]]s of order ''n'' is the smallest number of ''r''-edges such that every [[induced subgraph]] on ''k'' vertices contains an edge. This number was determined for ''r''&nbsp;=&nbsp;2 by {{harvtxt|Turán|1941}}, and the  problem for general ''r'' was introduced in {{harvtxt|Turán|1961}}. The paper {{harv|Sidorenko|1995}} gives a survey of Turán numbers.

==Definitions==
Fix a set ''X'' of ''n'' vertices. For given ''r'', an '''''r''-edge''' or '''block''' is a set of ''r'' vertices. A set of blocks is called a '''Turán (''n'',''k'',''r'') system''' (''n'' ≥ ''k'' ≥ ''r'') if every ''k''-element subset of ''X'' contains a block.
The  '''  Turán number''' T(''n'',''k'',''r'') is the minimum size of such a system.

==Example==
The complements of the lines of the [[Fano plane]] form a Turán (7,5,4)-system. T(7,5,4) = 7.<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg. 649, Example 61.3}}</ref>

==Relations to other combinatorial designs==
It can be shown that
::<math>T(n,k,r) \geq \binom{n}{r} {\binom{k}{r}}^{-1}.</math>
Equality holds if and only if there exists a [[Steiner system]] S(''n'' - ''k'', ''n'' - ''r'', ''n'').<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg. 649, Remark 61.4}}</ref>

An [[combinatorial design|(''n'',''r'',''k'',''r'')-lotto design]] is an (''n'', ''k'', ''r'')-Turán system. Thus, T(''n'',''k'', ''r'') = L(''n'',''r'',''k'',''r'').<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg. 513, Proposition 32.12}}</ref>

==See also==
*[[Forbidden subgraph problem]]
*[[Combinatorial design]]

==References==
{{reflist}}

===Bibliography===
* {{citation|last1=Colbourn|first1=Charles J.|last2=Dinitz|first2=Jeffrey H.|title=Handbook of Combinatorial Designs|year=2007|publisher=Chapman & Hall/ CRC|location=Boca Raton|isbn=1-58488-506-8|edition=2nd|url-access=registration|url=https://archive.org/details/handbookofcombin0000unse}}
*{{springerEOM|title=Turán number|first=A. P.|last= Godbole}}
*{{citation|first=A. |last=Sidorenko|title=What we know and what we do not know about Turán numbers|journal= [[Graphs and Combinatorics]] |volume= 11  |year=1995|issue=2|pages= 179–199	|doi=10.1007/BF01929486}}
*{{citation|last=Turán|first= P|year=1941|title= Egy gráfelméleti szélsőértékfeladatról (Hungarian. An extremal problem in graph theory.) |journal=Mat. Fiz. Lapok|volume= 48 |pages=436–452 |language= Hungarian}}
*{{citation|last=Turán|first= P.|title= Research problems|journal= Magyar Tud. Akad. Mat. Kutato Int. Közl.|volume=6|pages= 417–423 |year=1961}}

{{DEFAULTSORT:Turan Number}}
[[Category:Extremal graph theory]]
[[Category:Combinatorial design]]