Advanced graph theory

Relations:

In order to register for the course 01PTG, the student must have successfully completed the course 01TG in a previous semester.

Course guarantor:

Jan Volec

Lecturer:

Jan Volec

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

This course focuses on advanced topics of graph theory such as Szemerédi Regularity Lemma, Lovász Local Lemma, applications of concentration inequalities (Azuma-Hoeffding, Talagrand), polyhedral combinatorics, Galvin's „solution of the Dinitz problem“ and applications of linear algebra techniques in combinatorics.

Requirements:

Syllabus of lectures:

1. Submodularity of edge-cuts, Gomory-Hu trees.

2. Edmonds' algorithm for perfect matchings, Christofides' approximation algorithm for TSP.

3. List colorings / choosability: Thomassen's theorem, Alon's theorem, Galvin's solution of the Dinitz problem.

4. Erdős-Pósa property for cycles in graphs.

5. Perfect graphs, Lovász's Weak Perfect Graph Theorem.

6. Applications of linear algebra in combinatorics: Odd/even towns, existence of Moore graphs.

7. Concentration inequalities and their applications: counterexample to Hajós' conjecture,average degree vs. complete minors, connected components in Erdős-Rényi random graphs.

8. Lovász Local Lemma and its applications: Ramsey numbers, acyclic colorings of graphs, Strong chromatic number of a graph.

9. Szemerédi Regularity Lemma and its applications in combinatorics: Ruzsa–Szemerédi (6,3)-problem, removal lemmas, Roth's theorem on arithmetic progressions of length 3, Erdős-Stone theorem.

Syllabus of tutorials:

Study Objective:

Study materials:

[1] N. Alon, J. Spencer: The Probabilistic Method, Wiley, 2016.

[2] J. A. Bondy, U.S.R. Murty: Graph Theory, Springer-Verlag, 2008.

[3] Y. Zhao: Graph Theory and Additive Combinatorics, Cambridge University Press, 2023.

Note:

Further information:

http://honza.ucw.cz/PTG

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans: