Turán number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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 (nkr) 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[edit]

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[edit]

It can be shown that

Equality holds if and only if there exists a Steiner system S(n - k, n - r, n).[2]

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).[3]

See also[edit]

References[edit]

  1. ^ Colbourn & Dinitz 2007, pg. 649, Example 61.3
  2. ^ Colbourn & Dinitz 2007, pg. 649, Remark 61.4
  3. ^ Colbourn & Dinitz 2007, pg. 513, Proposition 32.12

Bibliography[edit]

  • Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8 
  • Godbole, A.P. (2001), "T/t120190", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 
  • Sidorenko, A. (1995), "What we know and what we do not know about Turán numbers", Graphs and Combinatorics, 11 (2): 179–199, doi:10.1007/BF01929486 
  • 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