Turán number

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 Turán (1941), and the problem for general $r$ was introduced in Turán (1961). The paper (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\geq k\geq 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.

Examples

The complements of the lines of the Fano plane form a Turán $(7,5,4)$ -system. $T(7,5,4)=7$ .^[2]

The following values and bounds for $T(n,6,4)$ are known:^[3]

$n$	7	8	9	10	11	12	13	14	15	16
$T(n,6,4)$	3	6	12	20	34	51	74–79	104–115	142–161	190–220

This sequence appears as (sequence A348464 in the OEIS).

The following values and bounds for $T(n,7,4)$ are known:^[3]

$n$	8	9	10	11	12	13	14	15	16
$T(n,7,4)$	2	5	10	17	26	38–39	54–56	74–80	99–108

It is also known that $T(17,5,4)\geq 627$ and $T(18,5,4)\geq 807$ ^[4]

Relations to other combinatorial designs

It can be shown that

T(n,k,r)\geq {\binom {n}{r}}{\binom {k}{r}}^{-1}.

Equality holds if and only if there exists a Steiner system $S(n-k,n-r,n)$ .^[5]

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)$ .^[6]

References

^ Colbourn & Dinitz 2007, pg. 649, Example 61.3
^ Colbourn & Dinitz 2007, pg. 649, Example 61.3
^ ^a ^b Sidorenko, Alexander (2021), "On Turán numbers of the complete 4-graphs", Discrete Mathematics, 344 (11) 112544, arXiv:2009.12955, doi:10.1016/j.disc.2021.112544
^ Markström, Klas (2009), "Extremal hypergraphs and bounds for the Turán density of the 4-uniform K5", Discrete Mathematics, 309 (16): 5231–5234, doi:10.1016/j.disc.2009.03.035
^ Colbourn & Dinitz 2007, pg. 649, Remark 61.4
^ Colbourn & Dinitz 2007, pg. 513, Proposition 32.12

Bibliography

Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
Godbole, A. P. (2001) [1994], "Turán number", Encyclopedia of Mathematics, EMS Press
Sidorenko, A. (1995), "What we know and what we do not know about Turán numbers", Graphs and Combinatorics, 11 (2): 179–199, doi:10.1007/BF01929486
Turán, P (1941), "Egy gráfelméleti szélsőértékfeladatról (Hungarian. An extremal problem in graph theory.)", Mat. Fiz. Lapok (in Hungarian), 48: 436–452
Turán, P. (1961), "Research problems", Magyar Tud. Akad. Mat. Kutato Int. Közl., 6: 417–423

[1] Colbourn & Dinitz 2007, pg. 649, Example 61.3

[2] Colbourn & Dinitz 2007, pg. 649, Example 61.3

[sid-3] Sidorenko, Alexander (2021), "On Turán numbers of the complete 4-graphs", Discrete Mathematics, 344 (11) 112544, arXiv:2009.12955, doi:10.1016/j.disc.2021.112544

[4] Markström, Klas (2009), "Extremal hypergraphs and bounds for the Turán density of the 4-uniform K5", Discrete Mathematics, 309 (16): 5231–5234, doi:10.1016/j.disc.2009.03.035

[5] Colbourn & Dinitz 2007, pg. 649, Remark 61.4

[6] Colbourn & Dinitz 2007, pg. 513, Proposition 32.12

[1]

[2]

[3]

[4]

[5]

[6]

Definitions

Examples

Relations to other combinatorial designs

See also

References

Bibliography