|
Instructor Course Schedule Topics and Prerequisites Final Exam and Requirements Exercises Course Progress |
| Piotr Micek | ||||
| Arnimallee 3, Rm 207 | ||||
| firstname.lastname at gmail.com | ||||
| 838-75205 |
| Lectures will take place in Takustr 9, Room 46, on Tuesdays from 14:15 to 15:45. Exercise classes will take place in Takustr 9, Room 55, on Wednesdays from 14:15 to 15:45. On the first week, the exercise class will be replaced with a second lecture. |
Topics |
Topics include: Graph Minor Theory: Tutte's lemma: generating 3-connected graphs; Kuratowski theorem: characterization of planar graphs; Mader's theorem: every graph with large average degree has a large clique minor; treewidth, brambles and tangles: treewidth duality theorem; excluded grid theorem; 2-disjoint rooted paths problem and Seymour's theorem; graph minor theorem for surfaces; statement(s) of the graph minor theorem. Sparsity: classes with bounded expansion; nowhere dense classes; characterisations, examples, current research. |
||
Prerequisites |
Discrete Mathematics I or equivalent (basic combinatorics and graph theory). | ||
Credits |
BMS: advanced course; FU Master: Discrete Mathematics III modul or Ergäzungsmodul. |
Homework assignments will be posted below, and should be submitted before 8:00am of the due day.
| Assignment | Due date | |
| Sheet 1 | 26/10/2016 | |
| Sheet 2 | 08/11/2016 | |
| Sheet 3 | 16/11/2016 | |
| Sheet 4 (updated 25/11 15:45) | 30/11/2016 | |
| Sheet 5 | 07/12/2016 | |
| Sheet 6 (Diestel's paper [pdf]) | 14/12/2016 | |
| Sheet 7 (a survey about tangles by Martin Grohe [pdf]; Graph Minors X by Neil Robertson and Paul Seymour[pdf]) | 18/01/2017 | |
| Sheet 8 (here are the videos of the series of lectures that I am following with you these days) | 25/01/2017 | |
| for the "Sheet 9", please watch Lecture 7 by Jim Geelen (Oct 3, 2016) and read section 12.5 of Diestel's book (5th edition!); among other things Geelen states an upgrade of the Grid Theorem: "A grid from a tange" or more precisely the theorem given around '35. As an exercise write down a sketch of the proof. As the second exercise I want you to understand the statement of the Tangle-Tree Theorem given at the same lecture and its proof given by Diestel. Is it the same proof as the one sketched by Geelen? I'm not sure ... | 01/02/2017 |