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

DOI10.1007/s10955-011-0336-2zbMath1231.82017arXiv1011.2945WikidataQ63953348 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 transitions; disordered systems; random graphs; cliques; probabilistic cellular automaton

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

82D30: Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses)

82B26: Phase transitions (general) in equilibrium statistical mechanics

68Q60: Specification and verification (program logics, model checking, etc.)

Related Items

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

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