Kombinatorika a grafy 3

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, více info u cvičícího (Ben Moore).

Plán přednášek
  • 3.10: Graph classes closed under subgraphs/minors/...
  • 10.10.: Minor-closed classes, Hadwiger's conjecture, average degrees.
  • 17.10.: Topological minors, Hajós' conjecture, linkedness.
  • 24.10.: Tree decompositions and treewidth.
  • 31.10.: Brambles, grid minors, ladder lemma and Erdős-Pósa theorem.
  • 7.11.: List coloring and polynomial method.
  • 14.11.: VC-dimension.
  • 21.11.: Spanning trees.
  • 28.11.: Epsilon-regular pairs and the formulation of the Regularity Lemma.
  • 5.12.: Applications of the Regularity Lemma.
  • 12.12. Proof of Regularity lemma.
  • 19.12.: Arithmetic Ramsey theory.
  • 2.1.: Treewidth in planar graphs and application to approximation algorithms (will not be part of the exam).
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):