Gibbs measures on sparse random graphs

Abstract

Many combinatorial optimization problems can be phrased in terms of Gibbs measures on labellings of the vertices of a graph. Techniques and insights from statistical physics have been applied in recent years to find the solvability thresholds as well as the structure of solutions for many of these problems. When the underlying graph is random, two key quantities of interest are the quenched and annealed free energy densities. The annealed free energy density is much easier to compute, and for some models, like the Ising ferromagnet, the quenched and annealed free energy densities agree at all temperatures. For others, the system undergoes a phase transition, and the two disagree at low temperature. We show this latter phenomenon is typical in the sense that for an open dense subset of interaction functions, on a random regular graph the quenched and annealed free energy densities of the associated Gibbs measure disagree for sufficiently low temperatures. We also present joint work with L. Bowen and F. Lin in which we consider a particular model, $2$-colorings of random regular hypergraphs, to answer an open problem in sofic entropy theory. A sofic approximation to a countable group is a sequence of partial actions on finite sets that asymptotically approximates the action of the group on itself by left-translations. A group is sofic if it admits a sofic approximation. Sofic entropy theory is a generalization of classical entropy theory in dynamics to actions by sofic groups. However, the sofic entropy of an action may depend on a choice of sofic approximation. All previously known examples showing this dependence rely on degenerate behavior. We exhibit an explicit example of a mixing subshift of finite type with two different positive sofic entropies.