Advanced graph theory
Code  Completion  Credits  Range  Language 

01PTG  ZK  2  2P+0C  Czech 
 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 (AzumaHoeffding, 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 edgecuts, GomoryHu 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ősPó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ősRé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ősStone 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, SpringerVerlag, 2008.
[3] Y. Zhao: Graph Theory and Additive Combinatorics, Cambridge University Press, 2023.
 Note:
 Further information:
 http://honza.ucw.cz/PTG
 No timetable has been prepared for this course
 The course is a part of the following study plans: