Material for the courses, made available by the instructors, will be
kept here. Come back often to check out for new material!
- Coloring sparse graphs with few colors, Alexandr Kostochka
- Supporting material
- Short proofs of coloring theorems on planar graphs
- On the minimal number of edges in color-critical graphs
- Extracting list colorings from large independent sets.
- Properties of Descartes’ construction of triangle-free graphs with high chromatic number.
- On the number of edges in colour-critical graphs and hypergraphs.
- Ore’s Conjecture on color-critical graphs is almost true.
- On the Minimum Number of Edges in Triangle-Free 5-Critical Graphs.
- Supporting material
- Graph limits and their applications in extremal combinatorics, Daniel Kráľ, lecture slides [Lecture 1, 2, 3, 4, 5]
- The perfect matching polytope, solid bricks and the perfect matching lattice, Cláudio L. Lucchesi [Lectures 1, 2, 3, 4]
- The method of hypergraph containers, Robert Morris
- Semidefinite programming upper-bounds for packing problems, Fernando Mário de Oliveira Filho (get also the exercise sheet)
- Semidefinite Programming Techniques in Combinatorial Optimization, Levent Tunçel [Exercises]
- Sample complexity and uniform convergence, Eli Upfal
- Recent progress in approximation algorithms for the traveling salesman problem, David Williamson, lecture slides [Lectures 1, 2, 3, and 4], annotated slides [Lectures 1, 2, 3, 4].
- The regularity method and blow-up lemmas for sparse graphs, Yoshiharu Kohayakawa, lecture slides [Lecture 1, 2, 3, 4]
- Suggested reading
- Kohayakawa, Y.; Rödl, V. Szemerédi’s regularity lemma and quasi-randomness. Recent advances in algorithms and combinatorics, 289–351, CMS Books Math./Ouvrages Math. SMC, 11, Springer, New York, 2003.
- Komlós, J.; Simonovits, M. Szemerédi’s regularity lemma and its applications in graph theory. Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295–352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
- Komlós, J.; Shokoufandeh, A.; Simonovits, M.; Szemerédi, E. The regularity lemma and its applications in graph theory. Theoretical aspects of computer science (Tehran, 2000), 84–112, Lecture Notes in Comput. Sci., 2292, Springer, Berlin, 2002.
- Rödl, V.; Schacht, M. Regularity lemmas for graphs. Fete of combinatorics and computer science, 287–325, Bolyai Soc. Math. Stud., 20, János Bolyai Math. Soc., Budapest, 2010.
- Komlós, J. The blow-up lemma. Recent trends in combinatorics (Mátraháza, 1995). Combin. Probab. Comput. 8 (1999), no. 1-2, 161–176.
- Komlós, J.; Sárközy, G. N.; Szemerédi, E. Blow-up lemma. Combinatorica 17 (1997), no. 1, 109–123.
- Komlós, J.; Sarkozy, G. N.; Szemerédi, E. An algorithmic version of the blow-up lemma. Random Structures Algorithms 12 (1998), no. 3, 297–312.
- Böttcher, J.; Kohayakawa, Y.; Taraz, A.; Würfl, A. An extension of the blow-up lemma to arrangeable graphs. SIAM J. Discrete Math. 29 (2015), no. 2, 962–1001.
- Conlon, D. Combinatorial theorems relative to a random set, Proceedings of the International Congress of Mathematicians 2014, Vol. 4, 303-328. [ICM Lecture]
- Schacht, M. Extremal results for random discrete structures, Ann. of Math. (2), to appear
- Conlon, D.; Gowers, W.T. Combinatorial theorems in sparse random sets, Ann. of Math. (2), to appear
- Conlon, D.; Gowers, W. T.; Samotij, W.; Schacht, M. On the KŁR conjecture in random graphs. Israel J. Math. 203 (2014), no. 1, 535–580.
- Balogh, J.; Morris, R.; Samotij, W. Independent sets in hypergraphs. J. Amer. Math. Soc. 28 (2015), no. 3, 669–709.
- Saxton, D.; Thomason, A. Hypergraph containers. Invent. Math. 201 (2015), no. 3, 925–992.
- Gerke, S.; Kohayakawa, Y.; Rödl, V; Steger, A. Small subsets inherit sparse ϵ-regularity. J. Combin. Theory Ser. B 97 (2007), no. 1, 34–56.
- Kohayakawa, Y.; Rödl, V. Regular pairs in sparse random graphs. Random Structures Algorithms 22 (2003), no. 4, 359–434.
- Kohayakawa, Y.; Rödl, V.; Schacht, M.; Szemerédi, E. Sparse partition universal graphs for graphs of bounded degree. Adv. Math. 226 (2011), no. 6, 5041–5065.
- Conlon, D.; Fox, J.; Zhao, Y. Extremal results in sparse pseudorandom graphs. Adv. Math. 256 (2014), 206–290.
- Allen, P.; Böttcher, J.; Hàn, H.; Kohayakawa, Y.; Person, Y. Blow-up lemmas for sparse graphs, preprint, 2016, 119pp.
- Suggested reading
- Combinatorial stochastic search and selection, Robert Kleinberg, lecture slides [Lecture 1, 2]
- Progression-free sets, the polynomial method, and arithmetic removal lemmas, Robert Kleinberg [Lecture slides]
- Harmonic analysis on polytopes and cones, Sinai Robins, lecture slides [Lectures 1, 2, 3, 4]
- Determining the rank of some graph convexities, Jayme L. Szwarcfiter
- Approximation Algorithms for Packing Circles, Flávio Keidi Miyazawa [also in handout format]