Turán number


In mathematics, the Turán number T 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, and the problem for general r was introduced in. The paper 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 system if every k-element subset of X contains a block.
The Turán number T is the minimum size of such a system.

Example

The complements of the lines of the Fano plane form a Turán -system. T = 7.

Relations to other combinatorial designs

It can be shown that
Equality holds if and only if there exists a Steiner system S.
An -lotto design is an -Turán system. Thus, T = L.