Kombinatorika a grafy 3

Přednáška středa 15:40 v S6, cvičení pondělí 15:40 na chodbě ve 3. patře.

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
  • 9.10.: Třídy grafů uzavřené na podstruktury. Cvičení; homework.
  • 16.10.: Minors and degrees. Topological minors, Hajós conjecture. Homework.
  • 23.10.: Linkedness and topological minors. Homework.
  • 30.10.: Tree decompositions, treewidth, brambles, grid minors. Homework.
  • 1.11.: Ladder lemma and Erdős-Pósa theorem.
  • 20.11.: Polynomial method. Homework.
  • 27.11.: VC-dimension.
  • 4.12.: Epsilon-regular pairs and the formulation of the Regularity Lemma. Homework.
  • 11.12.: Applications of the Regularity Lemma. Homework.
  • 18.12.: Proof of Regularity lemma.
  • 8.1.: Spanning trees.
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, English version.
Další zdroje

Domácí úkoly (rok 2016):

Domácí úkoly (rok 2015):

Anglické verze poznámek (rok 2014):