Gibbs measures and phase transitions on locally tree-like graphs
Abstract/Contents
- Abstract
- 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2014 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Sun, Nike |
|---|---|
| Associated with | Stanford University, Department of Statistics. |
| Primary advisor | Dembo, Amir |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Chatterjee, Sourav |
| Thesis advisor | Montanari, Andrea |
| Advisor | Chatterjee, Sourav |
| Advisor | Montanari, Andrea |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Nike Sun. |
|---|---|
| Note | Submitted to the Department of Statistics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2014. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2014 by Nike Sun
Also listed in
Loading usage metrics...