2025 Graduate Summer School Course Descriptions

Week 1 (July 6 - 12): Davin Conlon, Imre Leader, Jinyoung Park

Week 2 (July 13 - 19): Julian Sahasrabudhe, Matija Bucić, Will Perkins

Week 3 (July 20 - 26): Anita Liebenau, Sarah Peluse, Shachar Lovett

Matija Bucić, Institute for Advanced Study

Title: Sublinear expander graphs

Abstract: Expander graphs are certainly one of the most widely useful classes of graphs ever considered. In this course, we will explore a (weaker) notion of sublinear expansion due to Komlós and Szemerédi from the early 90's which has found a remarkable number of impressive applications in recent years.

We will start with a brief introduction to the theory of expander graphs, introduce the sublinear notion, show the pass to expander and expander decomposition lemma, establish a number of properties, and illustrate how they were used in some of the aforementioned recent applications.

Prerequisites: Familiarity with basic notions from graph theory, probability theory, and linear algebra.

David Conlon, Caltech

Title: Extremal Graph Theory

Abstract: Given a graph H and a natural number n, the extremal number ex(n, H) is the maximum number of edges in an H-free graph with n vertices. Though this function is reasonably well understood for non-bipartite H, an abundance of open questions remain for bipartite H. In this course, we will discuss some of the recent progress that has been made in this case. 

Imre Leader, University of Cambridge

Title:

Abstract:

Anita Liebenau, UNSW Sydney

Title: Enumeration of regular graphs

This course will explore techniques for the asymptotic enumeration of regular graphs, which have numerous applications beyond  counting, including generating graphs with specified degree sequences, aiding in network design and testing, enhancing our understanding of network dynamics, and modeling real-world systems. 

Existing asymptotic enumeration techniques can be roughly categorized into three methods: the configuration model and switchings, the use of generating functions combined with saddle point methods, and a relatively recent approach following Stein’s method, which utilizes degree switchings to derive recursive formulas. In this course, we will introduce all three methods, with a particular emphasis on the latter.

Prerequisites: Familiarity with basic discrete probability theory is assumed. Knowledge of concentration inequalities (Chernoff, Azuma-Hoeffding) is an advantage. No prior knowledge of enumerating graphs by degree sequence is assumed.

Shachar Lovett, University of California, San Diego

Title: From Sunflowers to Thresholds 

Abstract: A sunflower is a basic notion in combinatorics. A family of sets is called a sunflower if their pairwise intersections are all the same. The sunflower conjecture of Erdos and Rado is a fundamental open problem in combinatorics, which asks for the minimal size of a family of sets that must contain a sunflower of a given size. A few years ago, major progress was made on the conjecture, leveraging surprising connections to computational complexity. In follow up works, even more surprising connections were found to threshold phenomena, which eventually led to the resolution of the Kahn-Kalai conjecture, a major open problem in the area. 

In this series of talks, I will describe these results, with an emphasis on how connections between different fields of mathematics and theoretical computer science played a pivotal role. No specific prerequisites are needed except for mathematical maturity.

Jinyoung Park, NYU

Title: Asymptotic enumeration via graph containers and entropy

Abstract: The container methods are powerful tools to bound the number of independent sets of graphs and hypergraphs, and they have been extremely influential in the area of extremal and probabilistic combinatorics. We will focus on more specialized graph containers due to Sapozhenko (1987), that specifically deal with independent sets in expanders. Entropy, first introduced by Shannon (1948), from information theory is a measure of the expected amount of information contained in a random variable. Entropy has seen lots of fascinating applications in a wide range of enumeration problems.

In this series of lectures, we will discuss old and new applications of graph containers, entropy methods, and their combinations for various enumeration problems.

Introductory-level knowledge of combinatorics and probability will be assumed.

Sarah Peluse, Stanford University

Title: Arithmetic Ramsey theory

Abstract: This course will focus on a variety of Ramsey-theoretic questions concerning arithmetic configurations in abelian groups. After covering some classical results that can be proven by color focusing arguments, like van der Waerden's theorem guaranteeing monochromatic $k$-term arithmetic progressions in any finite coloring of the integers, we will introduce several modern tools from additive combinatorics and use them to prove that various linear and nonlinear configurations are density or partition regular, with good quantitative bounds.

Prerequisites: Some background in Fourier analysis (at least on finite abelian groups) would be helpful

Will Perkins, Georgia Tech

Title: Statistical physics approach to asymptotic enumeration and large deviations in random graphs

Abstract: This course will introduce some basics of statistical physics (Gibbs measures, partition functions, phase transitions) and some tools from statistical physics and algorithms (cluster expansion, coupling, Markov chain mixing) and apply these tools to study two related combinatorial problems: asymptotic enumeration of combinatorial structures (for example, counting the number of triangle-free graphs with a given edge density) and large deviations in random graphs (for example, the lower-tail large deviation problem for triangles in G(n,p)).  

Prerequisites: some probability theory (expectation, variance, central limit theorems, Markov chains, concentration inequalities).  No previous knowledge of statistical physics assumed or needed.

Optional background reading: Statistical Mechanics of Lattice Systems, Friedli & Velenik.  Markov Chains and Mixing Times, Levin & Peres.  The Method of Hypergraph Containers, Balogh, Morris, & Samotij.

Julian Sahasrabudhe, University of Cambridge

Title: Ramsey theory on Graphs

Abstract: This course will introduce several of the fundamental methods in modern combinatorics by focusing on Ramsey theory in the context of graphs. Interestingly, this one topic has inspired many techniques that have been used throughout combinatorics and beyond. In this course we will touch on a couple of these methods.