Turán number

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]

More information , ...

${\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

Close

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

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

More information , ...

${\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

Close

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]

• Forbidden subgraph problem
• Combinatorial design