Charting the replica symmetric phase (Q1749356)

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 factor graph models is given. Also, the authors give an asymptotic formula for the derivative of the free energy.