Turán number

The complements of the lines of the Fano plane, which form a Turán (7,5,4)-system. T(7,5,4) = 7. 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 Template:Harvtxt, and the problem for general $r$ was introduced in Template:Harvtxt. The paper Template:Harv 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\ge k\ge 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$.

The following values and bounds for $T(n,6,4)$ are known:Template:Sfnp

$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 Template:OEIS.

The following values and bounds for $T(n,7,4)$ are known:Template:Sfnp

$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)\ge 627$ and $T(18,5,4)\ge 807$Template:Sfnp

Relations to other combinatorial designs

It can be shown that

$T(n,k,r)\ge (\genfrac{}{}{0ex}{}{n}{r}){(\genfrac{}{}{0ex}{}{k}{r})}^{-1}.$

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

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)$.

Covering designs

The covering number $C(v,k,t)$ is the minimum number of $k$-element subsets of a $v$-set such that every $t$-element subset is contained in at least one of the chosen $k$-subsets. By passing to complementary subsets, covering numbers and Turán numbers are related by the identityTemplate:Sfnp

$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 $n$ large relative to $\ell$ and $r$, while covering problems typically have $n$ large relative to $n-r$ and $n-\ell$.Template:Sfnp

See also

• Forbidden subgraph problem
• Combinatorial design

References

• Template:Citation
• Template:SpringerEOM
• Template:Cite journal
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation