Statistical physics methods in combinatorics
The fields of combinatorics and statistical physics share some fundamental objects and concepts: graph polynomials correspond to partition functions; extremal constructions correspond to ground states; and "typical" combinatorial objects correspond to samples from a Gibbs measure. The goal of this lecture series will be to introduce the basics of the statistical physics perspective on partition functions, Gibbs measures, and phase transitions, and explain how this perspective (and the intuition from the study of physical systems) can be used to understand extremal, enumerative, and probabilistic questions in combinatorics. We will focus on independent sets in graphs as a running example, and see how to bound the size and number of independent sets in a graph, how to asymptotically enumerate independent sets in structured graphs, and how to understand the properties of a typical independent set in a graph using ideas and tools from statistical physics. No background in statistical physics is needed — we will cover the basic objects and notions in the course of the lectures.
Lecture plan
- Lecture 1: Statistical physics basics: Gibbs measures, partition functions, correlations, and phase transitions
- Lecture 2: Combinatorics and statistical physics
- Lecture 3: The cluster expansion
- Lecture 4: Independent sets in the hypercube
- Lecture 5: The algorithmic perspective
Background reading
- Friedli-Velenik: Statistical mechanics of lattice systems (Chapters 1,3,5 especially)
- Jenssen-Perkins: Independent sets in the hypercube revisited
- Davies-Jenssen-Perkins-Roberts: On the average size of independent sets in triangle-free graphs
