Kombinatorika a grafy 3
Přednáška: Čtvrtek 15:40–17:10 v S3. Cvičení: Čtvrtek 14:00–15:30 v S3.
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 (Guillaume Aubian).
Plán přednášek
- 5.10: Graph classes closed under subgraphs/minors/...: Lecture notes: Introduction and Section 1, excluding the parts on treedepth.
- 12.10.: Minor-closed classes, Hadwiger's conjecture, average degrees: Lecture notes: Everything except for section 4; we only started the proof from section 5, we will finish it in the next lecture.
- 19.10.: Topological minors, Hajós' conjecture, linkedness: Lecture notes: Sections 2 and 3; statement of Lemma 2 from these notes (the proof will be done in the next lecture).
- 26.10.: The proof of Lemma 2 left over from the previous lecture.
- 2.11.: Cancelled (sporting day).
- 9.11.: Tree decompositions and treewidth, brambles. Definition and Corollary 9 (with slightly different proof) from these lecture notes, section 1 from these. The results on brambles are only in the Czech notes (till the end of Section 1).
- 16.11. Grid minors, ladder lemma and Erdős-Pósa theorem. Lecture notes, sections 3 and 4.
- 23.11.: List coloring and polynomial method: Lecture notes. We got up to Theorem 6, the rest will be finished in the next lesson.
- 30.11.: Finished the Alon-Tarsi list coloring argument. VC-dimension (definition, examples, statement of Theorem 3 from the lecture notes.
- 7.12.: Application of VC-dimension to design of approximation algorithms (Corollary 4 from the lecture notes). Spanning trees (everything from the lecture notes).
- 14.12.: Epsilon-regular pairs and the formulation of the Regularity Lemma. Lecture notes.
- 21.12. Applications of the Regularity Lemma. Lecture notes.
- 4.1.: Arithmetic Ramsey theory. Section 1 from the lecture notes.
- 11.1.: Proof of Regularity lemma. Lecture notes.
Obsah přednášek a poznámky
- Epsilon-regulární páry
- Regularity lemma a jeho aplikace
- Další aplikace a důkaz Regularity lemmatu
- Hypergrafové removal lemma a aritmetická Ramseyovská teorie.
- Minory a stupně.
- Linkovanost a topologické minory.
- Erdős-Hajnalova hypotéza. Kografy.
- Stromové rozklady, chordální grafy, stromová šířka, Erdős-Pósova věta.
- Algoritmické aspekty stromové šířky.
- Kostry v grafech, English version.
- Polynomiální metoda, Nullstellensatz (plus úvod do seznamové barevnosti), English version.
- VC-dimenze, English version.
Další zdroje
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