Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
arXiv:1708.02457 · doi:10.1007/s10955-018-1964-6
Abstract
In two papers Franz, Leone and Toninelli proved bounds for the free energy of diluted random constraints satisfaction problems, for a Poisson degree distribution [5] and a general distribution [6]. Panchenko and Talagrand [16] simplified the proof and generalized the result of [5] for the Poisson case. We provide a new proof for the general degree distribution case and as a corollary, we obtain new bounds for the size of the largest independent set (also known as hard core model) in a large random regular graph. Our proof uses a combinatorial interpolation based on biased random walks [21] and allows to bypass the arguments in [6] based on the study of the Sherrington-Kirkpatrick (SK) model.
arXiv commentAccepted in Journal of Statistical Physics
References in corpus (8)
- Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
- The Thermodynamic Limit in Mean Field Spin Glass Models
- Tight bounds for LDPC and LDGM codes under MAP decoding
- Replica bounds for diluted non-Poissonian spin systems
- The hard-core model on random graphs revisited
- Replica bounds for optimization problems and diluted spin systems
- The interpolation method for random graphs with prescribed degrees
- Guerra's interpolation using Derrida-Ruelle cascades