Turán number

Turán number

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 harvtxt|Turán|1941, and the problem for general "r" was introduced in harvtxt|Turán|1961. The paper harv|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 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.

References

*springer|id=T/t120190|first=A.P.|last= Godbole
*citation|first=A. |last=Sidorenko|title=What we know and what we do not know about Turán numbers|journal= Graphs Combin. |volume= 11 |year=1995|pages= 179–199 |doi=10.1007/BF01929486
*citation|last=Turán|first= P|year=1941|title= Egy gráfelméleti szélsöértékfeladatról (Hungarian. An extremal problem in graph theory.) |journal=Mat. Fiz. Lapok|volume= 48 |pages=436-452 |lang= Hungarian
*citation|last=Turán|first= P.|title= Research problems|journal= Maguar Tud. Akad. Mat. Kutato Int. Közl.|volume=6|pages= 417–423 |year=1961


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Turán graph — The Turán graph T(13,4) Named after Pál Turán v · …   Wikipedia

  • Turan Dursun — (born 1934 died 4 September 1990) was first an Islamic scholar as an imam, and then a mufti in Turkey, before becoming an atheist during his study of the history of monotheistic religions. Dursun wrote a number of books about religion, which… …   Wikipedia

  • Turan Prince Residence — (Selimiye,Турция) Категория отеля: 5 звездочный отель Адрес: Side, 1276 Selimiye, Турция Описание: With its garden worthy of parad …   Каталог отелей

  • Turán's theorem — In graph theory, Turán s theorem is a result on the number of edges in a Kr+1 free graph. An n vertex graph that does not contain any (r + 1) vertex clique may be formed by partitioning the set of vertices into r parts of equal or… …   Wikipedia

  • Turán — Pál Turán, 1955 Pál Turán (auch: Paul Turán; * 28. August 1910 in Budapest; † 26. September 1976 ebenda) war ein ungarischer Mathematiker. Er lieferte Beiträge zu der Zahlentheorie, Gruppentheorie und der Approximationstheorie. Er bewie …   Deutsch Wikipedia

  • Turán sieve — In number theory, the Turán sieve is a technique for estimating the size of sifted sets of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Pál Turán in 1934.DescriptionIn terms of sieve… …   Wikipedia

  • Turan Plain — ▪ region, Central Asia Uzbek  Turon        extensive lowland in southwestern Kazakhstan and northwestern Uzbekistan and Turkmenistan. It is bounded by the Saryarqa (Kazakh uplands) in the north, the outliers of the Tien Shan, Pamir, and Alay… …   Universalium

  • Pál Turán — Paul (Pál) Turán Born 18 August 1910 …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Pál Turán — Pál Turán, 1955 Pál Turán (auch: Paul Turán; * 18. August 1910 in Budapest; † 26. September 1976 ebenda)[1] war ein u …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”