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, .
Covering designs
The covering number is the minimum number of -element subsets of a -set such that every -element subset is contained in at least one of the chosen -subsets. By passing to complementary subsets, covering numbers and Turán numbers are related by the identity
Although the two are thus equivalent, they have historically been studied in different parameter ranges: Turán problems typically have large relative to and , while covering problems typically have large relative to and .
See also Forbidden subgraph problem Combinatorial design
Notes
References