Charting the replica symmetric phase
type: Item
instance of: scholarly article
title: Charting the replica symmetric phase
zbMATH Open document ID: 1395.82039
author: Amin Coja-Oghlan
author: Charilaos Efthymiou
author: Nor Jaafari
author: Mihyun Kang
author: Tobias Kapetanopoulos
published in: Communications in Mathematical Physics
publication date: 2018-05-16T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7589/
review text: The authors are interested in a general class of random factor graph models, subject merely to a few easy-to-check assumptions. They develop a rigorous technique for the study of such models called the ``cavity method''. The authors indicate how the diluted \(k\)-spin model, the Potts antiferromagnet, and the stochastic block model fit into this framework. Also, the authors study models on sparse random graphs such as the Potts model on the Erdős-Rényi graph. The authors state the results on the condensation phase transition, the limiting distribution of the free energy, the overlap, the reconstruction and the detection thresholds for random factor graph models. As a functional, they study a version of the Bethe free energy from the cavity method. By using the cavity method, the authors study the existence of the condensation threshold \(d_\mathrm{cond}(k, \beta)\) for integers \(k\geq 2\) and at inverse temperature \(\beta\). They prove that for all \(\beta> 0\) and \(k\geq 4\) even, there exists \(d_{\mathrm{cond}}(k, \beta) = \inf \{ d> 0 : \lim \sup_{n\rightarrow \infty} \mathbb{E}\langle\varrho_{\sigma_1,\sigma_2}^2\rangle_{\mathbb{H},J,\beta}> 0\}.\) The authors illustrate their impact on three important examples: the diluted \(k\)-spin model, the Potts antiferromagnet on the random graph and the stochastic block model. Finally, the authors generalize the classical Kesten-Stigum upper bound for the reconstruction on trees given by \textit{H. Kesten} and \textit{B. P. Stigum} [Ann. Math. Stat. 37, 1463--1481 (1966; Zbl 0203.17402)]. The authors prove a conjecture about the detection problem in the stochastic block model that has received considerable attention [\textit{A. Decelle} et al., ``Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications'', Phys. Rev. E 84, 066106 (2011)]. The authors provide the upper-bound for \(d_{rec}\) and \(d^{*}_{rec}\). A concentration inequality for the free energy of the random f…
reviewed by: Hasan Akin
Mathematics Subject Classification ID: 82B20
Mathematics Subject Classification ID: 82B26
Mathematics Subject Classification ID: 81R40
Mathematics Subject Classification ID: 82B05
zbMATH DE Number: 6869093
zbMATH Keywords: cavity method
zbMATH Keywords: diluted mean-field models
zbMATH Keywords: Gibbs measure
zbMATH Keywords: condensation threshold
MaRDI profile type: Publication
OpenAlex ID: W2605280783
cites work: Community Detection and Stochastic Block Models
cites work: Q3467515
cites work: Reconstruction and Clustering in Random Constraint Satisfaction Problems
cites work: Bounds for Random Constraint Satisfaction Problems via Spatial Coupling
cites work: Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
cites work: On the 2-colorability of random hypergraphs
cites work: The two possible values of the chromatic number of a random graph
cites work: The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
cites work: Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
cites work: Random Regular Graphs: Asymptotic Distributions and Contiguity
cites work: Harnessing the Bethe free energy
cites work: Planting Colourings Silently
cites work: A positive temperature phase transition in random hypergraph 2-coloring
cites work: The condensation phase transition in random graph coloring
cites work: Decay of correlations for the hardcore model on the \(d\)-regular random graph
cites work: Random graphs.
cites work: Q3286850
cites work: Phase Transitions in Discrete Structures
cites work: On the Potts antiferromagnet on random graphs
cites work: Information-theoretic thresholds from the cavity method
cites work: The Number of Satisfying Assignments of Random Regulark-SAT Formulas
cites work: Antiferromagnetic Potts model on the Erdős-Rényi random graph
cites work: Satisfiability threshold for random regular \textsc{nae-sat}
cites work: Proof of the Satisfiability Conjecture for Large k
cites work: On the chromatic number of a random hypergraph
cites work: Relations between average case complexity and approximation complexity
cites work: On the Complexity of Random Satisfiability Problems with Planted Solutions
cites work: Bounds for diluted mean-fields spin glass models
cites work: Spatial Coupling as a Proof Technique and Three Applications
cites work: The high temperature region of the Viana-Bray diluted spin glass model
cites work: Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
cites work: Gibbs states and the set of solutions of random constraint satisfaction problems
cites work: Community detection thresholds and the weak Ramanujan property
cites work: Reconstruction on trees and spin glass transition
cites work: Information, Physics, and Computation
cites work: Q4237477
cites work: The freezing threshold for k-colourings of a random graph
cites work: The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
cites work: The phase transition in random regular exact cover
cites work: A proof of the block model threshold conjecture
cites work: Reconstruction and estimation in the planted partition model
cites work: Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
cites work: On the number of solutions in random hypergraph 2-colouring
cites work: Modern Coding Theory
cites work: Almost all cubic graphs are Hamiltonian
cites work: Component structure in the evolution of random hypergraphs
cites work: Reconstruction for the Potts model
DOI: 10.1007/S00220-018-3096-X
description: scientific article; zbMATH DE number 6869093