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 Turán (1941), and the problem for general r was introduced in Turán (1961). The paper (Sidorenko 1995) 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 ≥ k ≥ 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.
Example
The complements of the lines of the Fano plane form a Turán (7,5,4)-system. T(7,5,4) = 7.[1]
Relations to other combinatorial designs
It can be shown that
Equality holds if and only if there exists a Steiner system S(n - k, n - r, n).[2]
Turán, P (1941), "Egy gráfelméleti szélsőértékfeladatról (Hungarian. An extremal problem in graph theory.)", Mat. Fiz. Lapok (in Hungarian), 48: 436–452
Turán, P. (1961), "Research problems", Magyar Tud. Akad. Mat. Kutato Int. Közl., 6: 417–423