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:
Abstract:
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.