Turán nummer

I matematik är Turántalet T( n , k , r ) för r -uniforma hypergrafer av ordningen n det minsta antalet r -kanter så att varje inducerad subgraf på k hörn innehåller en kant. Detta tal bestämdes för r = 2 av Turán (1941) , och problemet för allmänt r introducerades i Turán (1961) . Tidningen ( Sidorenko 1995 ) ger en översikt över Turáns siffror.

Definitioner

Fixa en uppsättning X med n hörn. För given r är en r -kant eller block en uppsättning r hörn. En uppsättning block kallas ett Turán ( n , k , r ) system ( n ≥ k ≥ r ) om varje k -elementdelmängd av X innehåller ett block. Turántalet T ( n , k , r ) är minimistorleken på ett sådant system.

Exempel

Komplementen av linjerna i Fano-planet bildar ett Turán (7,5,4)-system. T(7,5,4) = 7.

Relationer till andra kombinatoriska mönster

Det kan man visa

$T(n,k,r)\geq {\binom {n}{r}}{\binom {k}{r}}^{-1}.$

Jämlikhet gäller om och endast om det finns ett Steinersystem S( n - k , n - r , n ).

En ( n , r , k , r )-lottodesign är ett ( n , k , r )-Turán-system. Således är T( n , k , r ) = L( n , r , k , r ).

Se även

• Förbjudet subgrafproblem
• Kombinatorisk design

Bibliografi

•   Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
• Godbole, AP (2001) [1994], "Turán nummer" , Encyclopedia of Mathematics , EMS Press
• Sidorenko, A. (1995), "Vad vi vet och vad vi inte vet om Turán-tal", Graphs and Combinatorics , 11 (2): 179–199, doi : 10.1007/BF01929486
• Turán, P (1941), "Egy gráfelméleti szélsőértékfeladatról (ungerska. Ett extremt problem inom grafteorin.)", Mat. Fiz. Lapok (på ungerska), 48 : 436–452
• Turán, P. (1961), "Forskningsproblem", Magyar Tud. Akad. Matta. Kutato Int. Közl. 6 : 417-423