Kombinatorika a grafy 3

Rozvržení: ..., cvičení ...

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
  • ...: Epsilon-regularni pary. Domácí úkoly.
  • ...: Regularity lemma a jeho aplikace.
  • ...: Další aplikace a důkaz Regularity lemmatu. Domácí úkoly.
  • ...: Hypergrafové removal lemma a Szemerediho veta.
  • ...: Minory a stupně. Domácí úkoly.
  • ...: Linkovanost a topologické minory. Domácí úkoly.
  • ...: Stromové rozklady, chordální grafy, stromová šířka. Domácí úkoly.
  • ...: Algoritmické aspekty stromové šířky. Domácí úkoly.
  • ...: Vybíravost grafu a Nullstellensatz. Domácí úkoly.
  • ...: Erdös-Hajnalova hypotéza, vlastnosti tříd grafů uzavřených na indukované podgrafy. Domácí úkoly.
  • ...: Kostry v grafech. Domácí úkoly.
  • ...: Aplikace pravděpodobnostní metody.
Obsah přednášek a poznámky
  1. Epsilon-regularni pary
  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.
  9. Algoritmické aspekty stromové šířky.
  10. Kostry v grafech.
  11. Vybíravost grafu a Nullstellensatz
Další zdroje

Domácí úkoly (rok 2015):

Anglické verze poznámek (rok 2014):