Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems

DOI10.1007/S10955-018-1964-6arXiv1708.02457MaRDI QIDQ6289901FDOQ6289901

Publication date: 8 August 2017

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.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics (82C41)

This page was built for publication: Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6289901)