Download or read book Gibbs Measures and Phase Transitions on Locally Tree-like Graphs written by Nike Sun and published by . This book was released on 2014 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: In this thesis we consider Gibbs measures defined on sparse, locally tree-like graphs. We investigate the asymptotic behavior of these measures in the limit of graph size tending to infinity. In the first part we study replica symmetric heuristics for the asymptotic free energy density. We develop an interpolation scheme for proving replica symmetric bounds, and apply it to establish new results on the free energy of some classical models of statistical physics, including the Ising, Potts, and hard-core models. In particular, for d even we explicitly determine the asymptotic free energy density of ferromagnetic Potts models on graphs converging locally to the d-regular tree. This result covers, for example, any sequence of d-regular graphs with diverging girth. In the second part of this thesis we study random constraint satisfaction problems in which replica symmetric heuristics are expected to fail. For a large class of these problems, the one-step replica symmetry breaking cavity heuristic yields exact predictions of the satisfiability transition. We give the first rigorous confirmations of this prediction for two problems in this class, not-all-equal-SAT and maximum independent set, both in the setting of random regular graphs. In the second problem we furthermore establish tight concentration of the maximum independent set size.