CO749 Introduction to Graph Minors
The following videos are the lectures of a topics course on graph minors given at the University of Waterloo in Fall 2016.
This course gives a detailed overview of the proof of the Graph Minors Structure Theorem of Neil Robertson and Paul Seymour. The proof is mostly based on the original techniques of Robertson and Seymour but also incorporates simplifications that arose in my work with Gerards and Whittle on matroid minors and other simplifications due to Kawarabayashi and Wollan.
- Lecture 1 (September 12): A brief introduction to graph minors and the definition of tree-width.
- Lecture 2 (September 14): Examples of "qualitative" structure theorems and the statement of the Graph Minors Structure Theorem.
- Lecture 3 (September 19): Embedding cliques in a surface, vortices, and branch-width.
- Lecture 4 (September 21): Highly connected sets and tangles.
- Lecture 5 (September 26): Proof of the Erdos-Posa Theorem.
- Lecture 6 (September 28): Proof of the Grid Theorem.
- Lecture 7 (October 3): The tree of tangles and crossings on a grid.
- Lecture 8 (October 5): Long jumps on a grid.
- Lecture 9 (October 14): Connectivity lemmas: A-paths and transversal paths.
- Lecture 10 (October 17): Controlling long jumps on a gridwork (wall subdivision).
- Lecture 11 (October 19): Controlling long jumps with an end near the boundary of a gridwork.
- Lecture 12 (October 24): The Two Paths Theorem and the Weak Structure Theorem (the Flat-Wall Theorem).
- Lecture 13 (October 26): Statement of the main structure theorem. (Structure relative to a tangle.)
- Lecture 14 (October 31): Representativity and distance in a surface.
- Lecture 15 (November 2): Finding a cylidrical grid minor around a hole. (See the correction at the start of Lecture 16.)
- Lecture 16 (November 7): Building a handle.
- Lecture 17 (November 9): Merging flat embeddings and filling a hole (part 1). (There was a mistake in merging flat embeddings; the correct versions of the two lemmas are given in the first two questions of Assignment 5.)
- Lecture 18 (November 14): Filling a hole (part 2).
- Lecture 19 (November 16): Planar regions with one vortex (part 1).
- Lecture 20 (November 21): Planar regions with one vortex (part 2) and surface grids (part 1).
- Lecture 21 (November 23): Surface grids (part 2).
- Lecture 22 (November 28): Surface grids (part 3).
- Lecture 23 (November 30): Bounding the number of holes.
- Lecture 24 (December 5): Overview. (The slides are available in PDF format.)
Here are the assignments.