Combinatorics Seminar (Fall 2024)

This is a weekly student-postdoc seminar on combinatorics at the Algorithms and the Complexity group at the Department of Computer Science, University of Copenhagen.

Week 1: Regularity Lemma - Why? What? How? by Amik Raj Behera

Resources: Notes by Yuval Wigderson, Notes by David Conlon, Talk by Jacob Fox

Week 2: Communication Complexity Lower Bounds via Rectangle Corruption by Jonas Conneryd

Week 3: Rank Lower Bounds via the Regularity Lemma by Théo Borém Fabris

Week 4: Eigenvalues of graphs and Sensitivity Conjecture by Egor Bakaev

Resources: Miniature 13 of Matoušek's book, Lecture by Timothy Gowers 

Week 5: Shearer's Entropy Lemma by Wietze Koops

Resources: Chapter 22 of Jukna's book

Week 6: Lovasz Local Lemma by Tuukka Korhonen

Resources: Lecture 2 and Lecture 3 of the course by Jan Vodrdak

Week 7:  Equivalent Definitions of Treewidth by Duri Andrea Janett

Week 8:  Spherical Cubes Through Cheeger's Inequality by Florestan Brunck

Resources

1. Extremal Combinatorics with Applications in Computer Science by Stasys Jukna

2. Collection of Problems in Extremal Combinatorics by Noga Alon: Part 1, Part 2, Part 3, Part 4

3. Extremal and Probabilistic Combinatorics by Robert Morris and Roberto Imbuzeiro Oliveira

4. Recent Developments in Extremal Combinatorics: Ramsey and Turan Type Problems by Benny Sudakov in ICM 2010, Hyderabad, India

5. A wonderful and massive collection of talks in Combinatorics by Igor Pak

6. A survey on the Polynomial Method and a course on the Polynomial Method by Larry Guth

7. Graph Theory and Additive Combinatorics by Yufei Zhao

8. Lecture Notes on Random Graphs by Yuval Filmus