Turánovo číslo - Turán number

V matematice je Turánovo číslo T (n,k,r) pro r-jednotný hypergrafy řádu n je nejmenší počet r- hrany takové, že každý indukovaný podgraf na k vrcholy obsahuje hranu. Toto číslo bylo určeno pro r = 2 od Turán (1941) a problém obecně r byl představen v Turán (1961). Papír (Sidorenko 1995 ) poskytuje přehled Turánových čísel.

Definice

Opravte sadu X z n vrcholy. Za dané r, an r-okraj nebo blok je sada r vrcholy. Sada bloků se nazývá a Turán (n,k,r) Systém (n ≥ k ≥ r) pokud každý k- podmnožina prvků X obsahuje blok Turánovo číslo T (n,k,r) je minimální velikost takového systému.

Příklad

Doplňky řádků Fano letadlo tvoří systém Turán (7,5,4). T (7,5,4) = 7.[1]

Vztahy k jiným kombinatorickým návrhům

To lze ukázat

Rovnost platí tehdy a jen tehdy, pokud existuje a Steinerův systém S (n - k, n - r, n).[2]

An (n,r,k,r) -lotto design je (n, k, r) -Turánský systém. Tedy T (n,k, r) = L (n,r,k,r).[3]

Viz také

Reference

  1. ^ Colbourn & Dinitz 2007, str. 649, příklad 61.3
  2. ^ Colbourn & Dinitz 2007, str. 649, poznámka 61.4
  3. ^ Colbourn & Dinitz 2007, str. 513, návrh 32.12

Bibliografie

  • Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Příručka kombinatorických vzorů (2. vyd.), Boca Raton: Chapman & Hall / CRC, ISBN  1-58488-506-8
  • Godbole, A.P. (2001) [1994], "Turánovo číslo", Encyclopedia of Mathematics, Stiskněte EMS
  • Sidorenko, A. (1995), „Co víme a co nevíme o Turánových číslech“, Grafy a kombinatorika, 11 (2): 179–199, doi:10.1007 / BF01929486
  • Turán, P (1941), „Egy gráfelméleti szélsőértékfeladatról (maďarsky. Extrémní problém v teorii grafů.)“, Rohož. Fiz. Lapok (v maďarštině), 48: 436–452
  • Turán, P. (1961), „Problémy výzkumu“, Magyar Tud. Akad. Rohož. Kutato Int. Közl., 6: 417–423