Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Advanced graph theory

The course is not on the list Without time-table
Code Completion Credits Range Language
01PTG ZK 2 2P+0C Czech

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

Garant předmětu:
Lecturer:
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
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2024-05-18
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet7850806.html