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

DOI10.1007/S10955-011-0336-2zbMATH Open1231.82017arXiv1011.2945OpenAlexW1925553027WikidataQ63953348 ScholiaQ63953348MaRDI QIDQ658477FDOQ658477

E. Scoppola, Benedetto Scoppola, Alexandre Gaudillière, Massimiliano Viale

Publication date: 12 January 2012

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

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.

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)

Cites Work

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

Cited In (9)

• Metastable states, quasi-stationary distributions and soft measures
• Phase transition and finite-size scaling in the vertex-cover problem
• Gaussian mean field lattice gas
• On independent sets in random graphs
• Overview: PCA Models and Issues
• Probabilistic cellular automata for low-temperature 2-d Ising model
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
• Sampling from a Gibbs measure with pair interaction by means of PCA
• Finding one community in a sparse graph

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)