Turán Number on:
[Wikipedia]
[Google]
[Amazon]
In mathematics, the Turán number T(''n'',''k'',''r'') for ''r''-uniform
In mathematics, the Turán number T(''n'',''k'',''r'') for ''r''-uniform hypergraph
In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
s of order ''n'' is the smallest number of ''r''-edges such that every induced subgraph
In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset.
Definition
Formally, let G=(V,E) ...
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 (''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 theFano plane
In finite geometry, the Fano plane (named after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and ...
form a Turán (7,5,4)-system. T(7,5,4) = 7.
Relations to other combinatorial designs
It can be shown that :: Equality holds if and only if there exists aSteiner system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner ...
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'').
See also
* Forbidden subgraph problem *Combinatorial design
Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of ''balance'' and/or ''symmetry''. These co ...
References
Bibliography
* * * * * {{DEFAULTSORT:Turan Number Extremal graph theory Combinatorial design