Advanced Graph Theory 01PTG (Spring 2024)
Email:  jan [AT] ucw [DOT] cz

Office:  T108a

Basic info
Literature (ENG)
 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
Lecture content
 20.2. –
List colorings and choosability, Thomassen's theorem, VoigtWirth'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, GallaiMilgram's theorem, Dilworth's theorem
 12.3. –
ErdősPósa theorem
 19.3. –
Submodularity of edgecuts and edgeconnectivity of vertextransitive graphs
 26.3. –
Discharging method, perfect graphs and weak perfect graph theorem
 2.4. –
Applications of linear algebra in combinatorics: Odd/EvenEven towns, GrahamPollak theorem, HoffmanSingleton theorem on (non)existence of Moore graphs
 9.4. –
The second moment method and Chebyshev inequality
 16.4. –
The 3point concentration of α(G_{n,½})
 23.4. –
Concentration inequalities (Chernoff), G_{n,½} is a.a.s. asymmetric
 30.4. –
Lovász local lemma and its applications – AlonLinial Theorem, Ramsey numbers
 7.5. –
Triangle removal lemma and Roth's theorem on 3APs, Szemeredi regularity lemma (without proof), Statement of the general graph removal lemma