Turán number

In mathematics, the Turán number ${\displaystyle T(n,k,r)}$ for ${\displaystyle r}$-uniform hypergraphs of order ${\displaystyle n}$ is the smallest number of ${\displaystyle r}$-edges such that every induced subgraph on ${\displaystyle k}$ vertices contains an edge. This number was determined for ${\displaystyle r=2}$ by Turán (1941), and the problem for general ${\displaystyle r}$ was introduced in Turán (1961). The paper (Sidorenko 1995) gives a survey of Turán numbers.

Fix a set ${\displaystyle X}$ of ${\displaystyle n}$ vertices. For given ${\displaystyle r}$, an ${\displaystyle r}$-edge or block is a set of ${\displaystyle r}$ vertices. A set of blocks is called a Turán ${\displaystyle (n,k,r)}$-system (${\displaystyle n\geq k\geq r}$) if every ${\displaystyle k}$-element subset of ${\displaystyle X}$ contains a block. The Turán number ${\displaystyle T(n,k,r)}$ is the minimum size of such a system.

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

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

${\displaystyle n}$	7	8	9	10	11	12	13	14	15	16
${\displaystyle 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 ${\displaystyle T(n,7,4)}$ are known:^[3]

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

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

It can be shown that

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

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

An ${\displaystyle (n,r,k,r)}$-lotto design is an ${\displaystyle (n,k,r)}$-Turán system. Thus, ${\displaystyle T(n,k,r)=L(n,r,k,r)}$.^[6]

The covering number ${\displaystyle C(v,k,t)}$ is the minimum number of ${\displaystyle k}$-element subsets of a ${\displaystyle v}$-set such that every ${\displaystyle t}$-element subset is contained in at least one of the chosen ${\displaystyle k}$-subsets. By passing to complementary subsets, covering numbers and Turán numbers are related by the identity^[7]

${\displaystyle T(n,\ell ,r)=C(n,\,n-r,\,n-\ell ).}$

Although the two are thus equivalent, they have historically been studied in different parameter ranges: Turán problems typically have ${\displaystyle n}$ large relative to ${\displaystyle \ell }$ and ${\displaystyle r}$, while covering problems typically have ${\displaystyle n}$ large relative to ${\displaystyle n-r}$ and ${\displaystyle n-\ell }$.^[7]

• Forbidden subgraph problem
• Combinatorial design

• 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
• Gordon, Daniel M.; Kuperberg, Greg; Patashnik, Oren (1995). "New constructions for covering designs" (PDF). Journal of Combinatorial Designs. 3 (4): 269–284. arXiv:math/9502238. doi:10.1002/jcd.3180030404.
• 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
• 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
• 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
• 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