Extremální teorie grafů

Extremální teorie grafů je oblastí teorie grafů, která zkoumá vztah kvantitativních parametrů konečných grafů. Extremální teorie grafů též může být vnímána jako obor extremální kombinatoriky, která zkoumá podobné problémy pro další diskrétní struktury (zejména pro množinové systémy a hypergrafy).

Historie

V roce 1941 dokázal Pál Turán slavnou Turánovu větu.[1] Tento okamžik je často považován za vznik extrámální teorie grafů, a to i přesto, že nejdůležitější trojúhelníkový případ Turánovy věty dokázal již v roce 1907 nizozemský matematik Willem Mantel.[2] Kolem Turána ovšem v Budapešti vznikla skupina mladých maďarských matematiků, kteří začali systematicky zkoumat problémy teorie grafů podobného typu. Do této skupiny patřil též Pál Erdős. Do sedmdesátých let dvacátého století se extremální teorie grafů rozvíjela převážně v Maďarsku. Mezi její nejvýznamnější představitele z tohoto období patřili Béla Bollobás a Endre Szemerédi. Jedním z hlavních důvodů internacionalizace oboru v sedmdesátých a osmdesátých letech dvacátého století byl odchod mnohých maďarských matematiků zejména do Spojených států.

Milníkem pro vývoj disciplíny byla Szemerédiho práce o aritmetických posloupnostech[3], která vedla k objevení regularity lemmatu, jednoho z nejdůležitějších nástrojů v moderní extremální teorie grafů. Právě tyto výsledky byly jedním z hlavních důvodů pro udělení Abelovy ceny Szemerédimu.

Související disciplíny

Počáteční rozvoj teorie grafů byl z velké části motivován otázkami v kombinatorické teorii čísel. Nejbližším oborem je teorie náhodných grafů, která se rozvíjela souběžně s extremální teorií grafů. Důvodem blízkosti těchto dvou disciplín je podobnost zkoumaných otázek a fakt, že výsledky v jednom z těchto oborů jsou aplikovatelné též ve druhém a v mnoha případech též podobnost metod použitelných k vyřešení problému. S tím souvisí, že pravděpodobnostní metoda hraje v extremální teorii grafů důležitou roli. Mnohé problémy studované v extremální teorii grafů přesahují do Ramseyovy teorie. V teoretické informatice je nejdůležitější použití extremální teorie grafů v oblasti testování vlastností.

Důležité výsledky a domněnky

Turánova věta udává optimální mez na počet hran ve grafu na daném počtu vrcholů, který zaručuje existenci úplného grafu jako podgrafu. Z mnoha zobecnění této věty je nejdůležitější věta Erdőse a Stonea[4], která určuje asymptoticky optimální mez pro obsahování libovolného nebipartitního grafu. Takzvaný Zarankiewiczův problém se táže na tu stejnou otázku pro bipartitní grafy. Přes to, že problém byl položen již v roce 1951, je pořád málo porozuměn.

Diracova věta říká, že pokud je minimální stupeň grafu alespoň polovina jeho řádu, pak je graf hamiltonovský.

V extremální teorii orientovaných grafů je nejdůležitějším problémem domněnka Caccetty a Häggkvista, která říká, že v orientovaném grafu na vrcholech a s minimálním stupněm alespoň obsahuje orientovaný cyklus délky nanejvýš .

Reference

  1. ↑ TURÁN, Paul. On an extremal problem in graph theory. Matematikai és Fizikai Lapok. 1941, roč. 48, s. 436–452. 
  2. ↑ MANTEL, Willem. Problem 28. Wiskundige Opgaven. 1907, roč. 10, s. 60–61. 
  3. ↑ SZEMERÉDI, Endre. On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica. 1975, s. 199–245. Dostupné online. (anglicky) 
  4. ↑ ERDŐS, P.; STONE, A. H. On the structure of linear graphs. Bulletin of the American Mathematical Society. 1946, s. 1087–1091. DOI 10.1090/S0002-9904-1946-08715-7. (anglicky)