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.

• 5.10.: Třídy grafů uzavřené na podstruktury. Minory a stupně. Domácí úkoly.
• 19.10.: Linkovanost a topologické minory. Domácí úkoly.
• 26.10.: Stromové rozklady a stromová šířka. Domácí úkoly.
• 2.11.: Stromová šířka a mřížkové minory. Erdős-Pósova věta. Domácí úkoly.
• 9.11.: Epsilon-regulární páry a formulace Regularity lemmatu. Domácí úkoly.
• 16.11.: Aplikace Regularity lemmatu. Domácí úkoly.
• 30.11.: Důkaz Regularity lemmatu. Domácí úkoly.
• 7.12.: Aritmetická Ramseyovská teorie. Domácí úkoly.
• 14.12.: Polynomiální metoda. Domácí úkoly.
• 21.12.: Kostry v grafech.
• 4.1.: VC-dimenze.

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

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