Held on Thursdays 12:20 on the 2nd floor corridor.

1. 24.2.: Introduction. Tangles, brambles, treewidth and minors.
2. 3.3.: Grid minor theorem.
3. 10.3.: Tangles in embedded graphs.
4. 17.3.: Linking in the disk and in the general surfaces (weak version).
5. 24.3.: Linking in the general surfaces, connection to respectful tangles.
6. 31.3.: The flat grid theorem and testing existence of a minor.
7. 7.4.: The basic ideas of the proof of the structure theorem.
8. 14.4.: Aplication of the structure theorem: Decomposition to bounded treewidth graphs.
9. 21.4.: Hadwiger's conjecture: Background, connectivity, relaxations.
10. 28.4.: Hadwiger's conjecture: Recent average degree improvements.
11. 5.5., 12.5., 19.5.: Reserve.

1. Introduction. Tangles, treewidth and minors. Lecture notes, presentation, homework assignment.
2. Towards the grid theorem: Statement, cleaning the grid, path-of-sets systems. Lecture notes, presentation, video of (most of) the lecture, homework assignment.
3. Further ideas of the proof of the grid theorem: Doubling the path-of-sets system, cleaning lemma. Lecture notes, presentation, video of the lecture, homework assignment.
4. Tangles in embedded graphs. Lecture notes, presentation, homework assignment.
5. Linking in the disk and in the general surfaces (weak version). Lecture notes, presentation, homework assignment.
6. Linking in the general surfaces, connection to respectful tangles. Lecture notes, presentation, homework assignment.
7. The flat grid theorem and testing existence of a minor. Lecture notes, presentation, homework assignment.
8. The basic ideas of the proof of the structure theorem. Lecture notes, presentation, homework assignment.
9. Aplication of the structure theorem: Decomposition to bounded treewidth graphs. Lecture notes, presentation, homework assignment.
10. Strengthening of the structure theorem, application: Bipartite minors in highly connected graphs. Lecture notes and the presentation.
11. Exam assignment: The structure theorem for forbidden topological minors.

Further topics (maybe):

• Linkedness in highly connected graphs.
• Isomorphism testing with forbidden minors and topological minors.
• Partial results on Hadwiger hypothesis (Connectivity of the minimal counterexamples, conditional algorithm, fractional version and other relaxations, recent average degree improvements).
• Large grids and sublinear cuts in graphs with forbidden minors, bidimensionality.

1. Opakování, definice, hlavní myšlenky a ingredience důkazu strukturální věty.
2. Stromová šířka a tangle.
3. Velká stromová šířka vynucuje velkou zeď.
4. Tangle a metrika na plochách.
5. Plochy a linkování.
6. Two Short Proofs Concerning Tree-Decompositions
7. 2-linkage a jejich zobecnění (transakce).
8. Rozšiřování vnoření.
9. Strukturální věta.
10. Testování existence minoru.
11. Stromové rozklady a dobré uspořádáni.
12. Plochy a dobré uspořádání.
13. Wagnerova hypotéza.

Doporučená literatura

• N. Robertson, P. Seymour: Graph Minors. I. - XXIII.
• N. Robertson, P. Seymour, R. Thomas: Quickly Excluding a Planar Graph, J. Comb. Theory, Ser. B (1994), 323-348.
• C. Thomassen: A simpler proof of the excluded minor theorem for higher surfaces, J.Combinatorial Theory B 70 (1997), 306-311.
• K. Kawarabayashi, P. Wollan: A simpler algorithm and shorter proof for the graph minor decomposition, STOC 2011, 451-458.
• M. Grohe, K. Kawarabayashi, D. Marx, P. Wollan: Finding topological subgraphs is fixed-parameter tractable, STOC 2011, 479-488.
• R. Diestel, T. Jensen, K. Gorbunov, C. Thomassen: Highly Connected Sets and the Excluded Grid Theorem, J. Comb. Theory, Ser. B (1999), 61-73.
• Julia Chuzhoy: Improved Bounds for the Flat Wall Theorem. SODA 2015: 256-275.

Další zdroje

• Poznámky k WQO
• Poznámky k tanglím a příklady ke cvičení.
• Velká stromová šířka vynucuje velkou zeď.
• Článek Two Short Proofs Concerning Tree-Decompositions
• Shrnutí - tangle v grafech na plochách.
• Minory v grafech na plochách.
• Přehled důkazu strukturální věty.