Turán number
File:Complement of the Fano plane.svg, which form a Turán (7,5,4)-system. T(7,5,4) = 7.{{harvnb|Colbourn|Dinitz|2007|loc=pg. 649, Example 61.3}} The graph is 4-uniform, order 7, and any 5 vertices selected induce an edge.]]
In mathematics, the Turán number T(n,k,r) for r-uniform hypergraphs 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 = 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.{{harvnb|Colbourn|Dinitz|2007|loc=pg. 649, Example 61.3}}
Relations to other combinatorial designs
It can be shown that
::
Equality holds if and only if there exists a Steiner system S(n - k, n - r, n).{{harvnb|Colbourn|Dinitz|2007|loc=pg. 649, Remark 61.4}}
An (n,r,k,r)-lotto design is an (n, k, r)-Turán system. Thus, T(n,k, r) = L(n,r,k,r).{{harvnb|Colbourn|Dinitz|2007|loc=pg. 513, Proposition 32.12}}
See also
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}}