Advanced Graph Theory 01PTG (Spring 2024)

• Tue 14:00 - 15:40 T-112

• Graph Theory – book by J.A. Bondy and U.S.R. Murty
• Graph Theory – book by R. Diestel (available online)
• Graph Theory and Additive Combinatorics – book by Y. Zhao (available online)
• The Probabilistic Method – book by N. Alon and J. Spencer
• Graph Colouring and the Probabilistic Method – book by M. Molloy and B. Reed

• 20.2. – List colorings and choosability, Thomassen's theorem, Voigt-Wirth's construction
• 27.2. – Alon's theorem on the list chromatic number vs the average degree, kernels in directed graphs, Galvin's theorem
• 5.3. – Proof of Richardson's theorem, Tournaments and theorems of Rédei and Camion, Gallai-Milgram's theorem, Dilworth's theorem
• 12.3. – Erdős-Pósa theorem
• 19.3. – Submodularity of edge-cuts and edge-connectivity of vertex-transitive graphs
• 26.3. – Discharging method, perfect graphs and weak perfect graph theorem
• 2.4. – Applications of linear algebra in combinatorics: Odd/Even-Even towns, Graham-Pollak theorem, Hoffman-Singleton theorem on (non-)existence of Moore graphs
• 9.4. – The second moment method and Chebyshev inequality
• 16.4. – The 3-point concentration of α(G_n,½)
• 23.4. – Concentration inequalities (Chernoff), G_n,½ is a.a.s. asymmetric
• 30.4. – Plan: Lovász local lemma and its applications – diagonal Ramsey numbers, off-diagonal Ramsey Numbers, Alon-Linial Theorem
• 7.5. – Plan: Triangle removal lemma and Roth's theorem on 3-APs, Szemeredi regularity lemma (without proof), graph removal lemma, Erdős-Stone Theorem