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 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