- 2019.01.21. Fourth homework and all exercises from tutorials. Updated list of topics for the oral exam.
- 2019.01.02. Topics for the oral exam.
- 2018.12.17. All exercises up to today and third homework. The results of the second homework are in USOS.
- 2018.11.19. All exercises up to today and second homework. The results of the first homework are in USOS.
- 2018.11.13. Update of the schedule due to 12.11 being an unexpected holiday.
- 2018.10.15. Exercises from the first two meetings and first homework.
- 2018.09.12. Setting up.

Course in USOS.

Webpage of the first edition, webpage of the second edition.

- Final grade is based on homeworks and final oral exam.
- We plan four homework assignments, each consisting of at least three problems. Each homework assignment should be submitted either by email or in a hard copy at the lecture on the day of the deadline.
- Each homework problem is worth 10 points. At the end of the semester we give a tentative grade, based on the number of points from the homework. We guarantee that 40 points will be enough for a passing grade.
- During the oral exam, one can modify the tentative grade by one of the values -1, -0.5, 0, +0.5, +1.0, +1.5. Not attending the exam results in the -1 modifier. If the final grade is lower than 3, it becomes 2.

- Graphs on surfaces (2 lectures)
- Graph minors (6 lectures)
- Expanders (4 lectures)
- Colourings (2 lectures)

No | Date | Plan | Notes |
---|---|---|---|

1 | 8.10 | Embeddings of graphs on surfaces. Combinatorial embeddings. Genus. Finding shortest noncontractible cycle in an embedded graph. | |

2 | 15.10 | Embeddings continued. Embeddings of large face-width. | Announcing first homework assignment. |

3 | 22.10 | Introduction to the theory of graph minors. Treewidth. | |

4 | 29.10 | Brambles and well-linked sets. | |

5 | 5.11 | Tangles. Kruskal's theorem. | Deadline of the first homework assignment. |

6 | 19.11 | Structure theorem for graphs excluding a fixed minor. Sketch of the Robertson-Seymour theorem. | Announcing second homework assignment. |

7 | 26.11 | Grid minor theorem. | |

8 | 3.12 | Graph minors in planar graphs. Linear grid minor theorem. The ratcatcher algorithm. | |

9 | 10.12 | Introduction to expanders. | Deadline of the second homework assignment. |

10 | 17.12 | Random walks in expanders. | Announcing third homework assignment. |

11 | 07.01 | The zig-zag product of graphs. | |

12 | 14.01 | Proof that undirected reachability is in LOGSPACE (L=SL). | |

13 | 21.01 | Colourings of planar graphs. The five- and four-colour theorem. Five-choosability of planar graphs. Discharging. Perfect graphs. | Announcing fourth homework assignment. Deadline of the third homework assignment. |

No | Announced | Deadline |
---|---|---|

Assignment 1 | 15.10 (lecture 1) | 5.11 (lecture 5) |

Assignment 2 | 19.11 (lecture 6) | 10.12 (lecture 9) |

Assignment 3 | 17.12 (lecture 10) | 21.01 (lecture 13) |

Assignment 4 | 21.01 (lecture 13) | 4.02 (Monday, 2nd week of exam session) |

- Reinhard Diestel, Graph Theory, Springer-Verlag 2005. PDF version.
- Bela Bollobas, Modern Graph Theory, Springer 1998.
- Mike Krebs, Anthony Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, USA, 2011.
- Bojan Mohar, Carsten Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001.
- Some papers on the web, such as:
- Shlomo Hoory, Nathan Linial, Avi Wigderson, Expander Graphs and Their Applications, Bulletin of AMS 2006. PDF
- Michael A. Nielsen, Introduction to Expander Graphs, 2005. PDF
- Omer Reingold, Salil Vadhan, and Avi Wigderson, Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors, 2001. PS
- Laszlo Lovasz, Graph Minor Theory, Bulletin of AMS 2005. PDF
- Petr Hlineny, Discharging Technique in Practice. PS