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.

The complements of the lines of the Fano plane, which form a Turán (7,5,4)-system. T(7,5,4) = 7.^[1] The graph is 4-uniform, order 7, and any 5 vertices selected induce an edge.

Definitions

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.

Examples

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]

Relations to other combinatorial designs

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]

See also

• Forbidden subgraph problem
• Combinatorial design