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