Phase transitions for the cavity approach to the clique problem on random graphs

DOI10.1007/s10955-011-0336-2zbMath1231.82017arXiv1011.2945OpenAlexW1925553027WikidataQ63953348 ScholiaQ63953348MaRDI QIDQ658477

Alexandre Gaudillière, Massimiliano Viale, Elisabetta Scoppola, Benedetto Scoppola

Publication date: 12 January 2012

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.2945

zbMATH Keywords

phase transitionsdisordered systemsrandom graphscliquesprobabilistic cellular automaton

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Phase transitions (general) in equilibrium statistical mechanics (82B26) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (7)

Metastable states, quasi-stationary distributions and soft measures ⋮ On independent sets in random graphs ⋮ Overview: PCA Models and Issues ⋮ Finding one community in a sparse graph ⋮ Sampling from a Gibbs measure with pair interaction by means of PCA ⋮ Probabilistic cellular automata for low-temperature 2-d Ising model ⋮ Gaussian mean field lattice gas

Cites Work

• Sampling the Fermi statistics and other conditional product measures
• Some spin glass ideas applied to the clique problem
• Metastability for a stochastic dynamics with a parallel heat bath updating rule
• Statistical mechanics of probabilistic cellular automata.
• On independent sets in random graphs

This page was built for publication: Phase transitions for the cavity approach to the clique problem on random graphs