Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
Preprint
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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Local Algorithms, Regular Graphs of Large Girth, and Random Regular GraphsCombinatorica, 2018
- Maximum independent sets on random regular graphsActa Mathematica, 2016
- The Interpolation Method for Random Graphs with Prescribed DegreesCombinatorics, Probability and Computing, 2015
- The Probability That a Random Multigraph is SimpleCombinatorics, Probability and Computing, 2009
- Bounds for diluted mean-fields spin glass modelsProbability Theory and Related Fields, 2004
- Replica bounds for diluted non-Poissonian spin systemsJournal of Physics A: General Physics, 2003
- Replica Bounds for Optimization Problems and Diluted Spin SystemsJournal of Statistical Physics, 2003
- Broken Replica Symmetry Bounds in the Mean Field Spin Glass ModelCommunications in Mathematical Physics, 2003
- A mathematical reformulation of Derrida's REM and GREMCommunications in Mathematical Physics, 1987
- A sequence of approximated solutions to the S-K model for spin glassesJournal of Physics A: General Physics, 1980