Kombinatorika a grafy 3

Tento semestr nevyučuji.

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
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 aritmetická Ramseyovská teorie.
  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. Polynomiální metoda, Nullstellensatz (plus úvod do seznamové barevnosti)
  12. VC-dimenze
Další zdroje

Domácí úkoly (rok 2016):

Domácí úkoly (rok 2015):

Anglické verze poznámek (rok 2014):