Turán number

From Wikipedia, the free encyclopedia

In mathematics, the Turán number T(n,k,r) for r-graphs of order n is the smallest number of r-edges such that every set of 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. ́

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

[edit] References

• Godbole, A.P. (2001), “Turán number”, in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104 
• Sidorenko, A. (1995), “What we know and what we do not know about Turán numbers”, Graphs Combin. 11: 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 48: 436-452 
• Turán, P. (1961), “Research problems”, Maguar Tud. Akad. Mat. Kutato Int. Közl. 6: 417–423