Limits of discrete distributions and Gibbs measures on random graphs
arXiv:1512.06798 · doi:10.1016/j.ejc.2017.06.012
Abstract
Building upon the theory of graph limits and the Aldous-Hoover representation and inspired by Panchenko's work on asymptotic Gibbs measures (Annals of Probability 2013), we construct continuous embeddings of discrete probability distributions. We show that the theory of graph limits induces a meaningful notion of convergence and derive a corresponding version of the Szemerédi regularity lemma. Moreover, complementing recent work (Bapst et. al. 2015), we apply these results to Gibbs measures induced by sparse random factor graphs and verify the "replica symmetric solution" predicted in the physics literature under the assumption of non-reconstruction.
References in corpus (13)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Graph limits and exchangeable random graphs
- An Extended Variational Principle for the SK Spin-Glass Model
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Spin glass models from the point of view of spin distributions
- Large deviations of empirical neighborhood distribution in sparse random graphs
- Factor models on locally tree-like graphs
- The condensation phase transition in random graph coloring
- Harnessing the Bethe free energy
- Limits of compact decorated graphs
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees