Turán number

In mathematics, the Turán number for -uniform hypergraphs of order is the smallest number of -edges such that every induced subgraph on vertices contains an edge. This number was determined for by, and the problem for general was introduced in. The paper gives a survey of Turán numbers.

Definitions

Fix a set of vertices. For given, an -edge or block is a set of vertices. A set of blocks is called a Turán -system if every -element subset of contains a block.
The Turán number is the minimum size of such a system.

Examples

The complements of the lines of the Fano plane form a Turán -system..
The following values and bounds for are known:

	7	8	9	10	11	12	13	14	15	16
	3	6	12	20	34	51	74–79	104–115	142–161	190–220

This sequence appears as.
The following values and bounds for are known:

	8	9	10	11	12	13	14	15	16
	2	5	10	17	26	38–39	54–56	74–80	99–108

It is also known that and

Relations to other combinatorial designs

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