Combinatorics Seminar (Spring 2024)
This is a weekly student-postdoc seminar on combinatorics at the Algorithms and the Complexity and Game Theory group at the Department of Computer Science, Aarhus University.
Week 1: Combinatorial Nullstellensatz by Amik Raj Behera
Resources: Paper by Noga Alon, Slides by Evan Chen
Week 2: Information Theory in Combinatorics by Sudarshan Shyam
Resources: Article by Jaikumar Radhakrishnan
Week 3: Complete Chaos is Impossible - A short and biased introduction to Ramsey Theory by Aniket Basu Roy
Week 4: Bollobas Lemma by Zhile Jiang
Resources: Talks by Fedor V. Fomin - Talk 1, Talk 2, Talk 3, Talk 4
Week 5: Generating Functions by Magnus Christian Ring Merrild
Week 6: Discrepancy and Spencer's upper bound by Mikael Møller Høgsgaard
Resources: Lecture note
Week 7: Applications of Pigeonhole Principle by Karl Albert Friedrich Fehrs
Resources: Chapter 4 of Extremal Combinatorics by Stasys Jukna
Week 8: Counting Principles by Magnus Christian Ring Merrild
Week 9: Regularity Lemma by Arthur da Cunha
Resources: Blog Post by Terrence Tao
Week 10: Lower Bounds in Algorithmic Game Theory by Sebastian Homrighausen
Resources: Chapter 7 of Tim Roughgarden's Lecture Notes
Week 11: Sunflower Lemma and its Applications by Amik Raj Behera
Resources: Chapter 6 of Extremal Combinatorics by Stasys Jukna, Talk by Shachar Lovett
Week 12: Erdos-Renyi Graphs by Andrew Alexander Draganov
Resources: The Diameter of the Minimum Spanning Tree of a Complete Graph
Week 13: Martingales by Sudarshan Shyam
Week 14: Helly's Theorem and its applications in geometry by Aniket Basu Roy
Resources: Chapter 1 of Lectures on Discrete Geometry by Jiří Matoušek
Week 15: Helly's Theorem and LP type problems by Jens Kristian Refsgaard Schou
Resources
Extremal Combinatorics with Applications in Computer Science by Stasys Jukna
Collection of Problems in Extremal Combinatorics by Noga Alon: Part 1, Part 2, Part 3, Part 4
Extremal and Probabilistic Combinatorics by Robert Morris and Roberto Imbuzeiro Oliveira
Recent Developments in Extremal Combinatorics: Ramsey and Turan Type Problems by Benny Sudakov in ICM 2010, Hyderabad, India
A wonderful and massive collection of talks in Combinatorics by Igor Pak
A survey on the Polynomial Method and a course on the Polynomial Method by Larry Guth
Graph Theory and Additive Combinatorics by Yufei Zhao
Lecture Notes on Random Graphs by Yuval Filmus