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

DOI10.1007/S10955-011-0336-2MaRDI QIDQ658477zbMATH OpenOpenAlexWikidataFDO

Authors Alexandre Gaudillière, Massimiliano Viale, Benedetto Scoppola, E. 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) Specification and verification (program logics, model checking, etc.) (68Q60) Phase transitions (general) in equilibrium statistical mechanics (82B26) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Abstract: We give a rigorous proof of two phase transitions for a disordered system designed to find large cliques inside Erdos random graphs. Such a system is associated with a conservative probabilistic cellular automaton inspired by the cavity method originally introduced in spin glass theory.

Recommendations

• Phase transitions in discrete structures
• The condensation phase transition in random graph coloring
• Some spin glass ideas applied to the clique problem
• Phase transitions in discrete structures
• The condensation phase transition in random graph coloring

Cites work

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

Cited in

(13)

• Finding one community in a sparse graph
• Metastable states, quasi-stationary distributions and soft measures
• Phase transition and finite-size scaling in the vertex-cover problem
• Overview: PCA models and issues
• Phase transitions in discrete structures
• Some spin glass ideas applied to the clique problem
• Gaussian mean field lattice gas
• Parallel tempering for the planted clique problem
• Properties of atypical graphs from negative complexities
• Gibbs measures and phase transitions on sparse random graphs
• Probabilistic cellular automata for low-temperature 2-d Ising model
• Sampling from a Gibbs measure with pair interaction by means of PCA
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

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

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