Statistical Physics, Interpolation Method and Scaling Limits in Sparse Random Graphs

Statistical physics, provided powerful insights into the theory of combinatorial structures and algorithms. For example, the success of certain counting algorithms is well known to be linked with the phase transition properties of the underlying combinatorial model.

Recently, however, a new powerful method was developed in the statistical physics of spin glasses, based on the interpolation idea. Among other things, the interpolation method was used to prove the existence of the so-called free energy thermodynamic limits for several spin glass models. In this talk we will discuss applications of the interpolation method in the context of combinatorial optimization problems on sparse random graphs. Using this method we establish the existence of scaling limits for a variety of combinatorial problems, including Maximum Independent Set, MAX-CUT, Coloring, K-SAT, and related problems. For these models, we show that the optimal values, appropriately normalized, converge to a limit with high probability, as the size of the underlying graph diverges to infinity. For the case of Independent Set model, this resolves a problem which was proposed by David Aldous in 2000 as one of his six favorite open problems. The talk will be completely self-contained. No background on the theory of random graphs or statistical physics is necessary.

Joint work with Mohsen Bayati (Stanford) and Prasad Tetali (Georgia Tech).