Lecture: Monday 10:40 in S11. Tutorials (Dinis Vitorino): Tuesday 10:40 in S7.

Conditions to pass the tutorials: Getting sufficiently many points for active participation; for more details, contact Dinis Vitorino who leads the tutorials.

• 5.10. [ZD]: Graph classes closed under subgraphs/minors/...: Lecture notes: Introduction and Section 1, excluding the parts on treedepth.
• 12.10. [ZD]: Minor-closed classes, Hadwiger's conjecture, average degrees: Lecture notes: Everything except for section 4.
• 19.10. [ZD]: Topological minors, Hajós' conjecture, linkedness: Lecture notes: Sections 2 and 3; Lemma 2 from these notes.
• 26.10. [ZD]: Tree decompositions and treewidth, brambles. Definition and Corollary 9 (with slightly different proof) from these lecture notes, section 1 from these. See these notes for the results on brambles, till the end of Section 1.
• 2.11. [ZD]: Grid minors, ladder lemma, Courcelle's theorem. Lecture notes, section 2, and these notes, section 1.
• 9.11. [??]: List coloring and polynomial method: Lecture notes, only the part on Alon-Tarsi method.
• 16.11. [??]: VC-dimension (definition, examples, statement of Theorem 3, application to approximation algoritms from the lecture notes).
• 23.11. [??]: Spanning trees (everything from the lecture notes).
• 30.11. [RŠ]: Epsilon-regular pairs and the formulation of the Regularity Lemma. Lecture notes.
• 7.12. [RŠ]: Applications of the Regularity Lemma. Lecture notes.
• 14.12. [RŠ]: Arithmetic Ramsey theory. Section 1 from the lecture notes.
• 4.1. [RŠ]: Proof of Regularity lemma. Lecture notes.

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, English version.
11. Polynomiální metoda, Nullstellensatz (plus úvod do seznamové barevnosti), English version.
12. VC-dimenze, English version.

Domácí úkoly (rok 2016):

• Minory a stupně.
• Linkovanost a topologické minory.
• Stromové rozklady, chordální grafy, stromová šířka.
• Algoritmické aspekty stromové šířky.
• Erdős-Hajnalova hypotéza, vlastnosti tříd grafů uzavřených na indukované podgrafy.
• Kostry v grafech.
• Epsilon-regulární páry.
• Další aplikace a důkaz Regularity lemmatu.
• Vybíravost grafu a Nullstellensatz.

Domácí úkoly (rok 2015):

• Epsilon-regularita
• Regularity lemma a jeho aplikace
• Další aplikace a důkaz Regularity lemmatu
• Hypergrafové removal lemma a Szemerédiho veta.
• Minory a stupně.
• Linkovanost a topologické minory.
• Erdős-Hajnalova hypotéza. Kografy.
• Stromové rozklady, chordální grafy, stromová šířka.
• Algoritmické aspekty stromové šířky.
• Kostry v grafech.

Anglické verze poznámek (rok 2014):

• Characterizations of graph classes by forbidden configurations
• Cographs; chordal graphs and tree decompositions
• Tree-width
• Tree-width and algorithms
• Monadic Second Order Logic
• Minors, topological minors and degrees
• Connectivity and linkedness
• List coloring
• Regularity lemma - statement, regular pairs and their properties
• Regularity lemma - applications
• Arithmetic Ramsey Theory