Statistical Physics Approach to Asymptotic Enumeration and Large Deviations in Random Graphs - Part 1

Explore the intersection of statistical physics and combinatorics in this 58-minute lecture that introduces fundamental concepts from statistical physics including Gibbs measures, partition functions, and phase transitions. Learn essential tools from statistical physics and algorithms such as cluster expansion, coupling, and Markov chain mixing, then apply these methods to tackle two interconnected combinatorial problems: asymptotic enumeration of combinatorial structures (exemplified by counting triangle-free graphs with specific edge densities) and large deviations in random graphs (demonstrated through the lower-tail large deviation problem for triangles in G(n,p)). Gain insights into how statistical physics approaches can provide powerful solutions to complex enumeration and probability problems in graph theory. The presentation assumes familiarity with probability theory concepts including expectation, variance, central limit theorems, Markov chains, and concentration inequalities, while requiring no prior knowledge of statistical physics. This lecture forms part of the IAS-PCMI Graduate Summer School on Probabilistic and Extremal Combinatorics, emphasizing the strong connections between combinatorics and other mathematical areas including analysis, geometry, number theory, statistical physics, and theoretical computer science.