Kombinatorika a grafy 3

Rozvržení: přednáška čtvrtek 9:00 v S10, cvičení pondělí 12:20 v S6.

Podmínky získání zápočtu: za řešení domácích úkolů a aktivní účast na cvičeních.

Plán přednášek
  • 5.10.: Třídy grafů uzavřené na podstruktury. Minory a stupně. Domácí úkoly.
  • 19.10.: Linkovanost a topologické minory. Domácí úkoly.
  • 26.10.: Stromové rozklady a stromová šířka. Domácí úkoly.
  • 2.11.: Stromová šířka a mřížkové minory. Erdős-Pósova věta. Domácí úkoly.
  • 9.11.: Epsilon-regulární páry a formulace Regularity lemmatu. Domácí úkoly.
  • 16.11.: Aplikace Regularity lemmatu. Domácí úkoly.
  • 30.11.: Důkaz Regularity lemmatu.
  • 7.12.: Aritmetická Ramseyovská teorie.
  • 14.12.: Nullstellensatz a jeho aplikace.
  • 21.12.: Kostry v grafech.
  • 4.1.: Aplikace pravděpodobnostní metody.
  • 11.1.: VC-dimenze.
Obsah přednášek a poznámky
  1. Epsilon-regulární páry
  2. Regularity lemma a jeho aplikace
  3. Další aplikace a důkaz Regularity lemmatu
  4. Hypergrafové removal lemma a Szemerediho veta.
  5. Minory a stupně.
  6. Linkovanost a topologické minory.
  7. Erdős-Hajnalova hypotéza. Kografy.
  8. Stromové rozklady, chordální grafy, stromová šířka, Erdős-Pósova věta.
  9. Algoritmické aspekty stromové šířky.
  10. Kostry v grafech.
  11. Vybíravost grafu a Nullstellensatz
Další zdroje

Domácí úkoly (rok 2016):

Domácí úkoly (rok 2015):

Anglické verze poznámek (rok 2014):