2014/07/31 by Alberto Guggiola, Guilhem Semerjian · 2 citations
Mathematics · Physics and Astronomy · #1-planar graph #Chordal graph #Combinatorics #Complex Network Analysis Techniques #Constraint satisfaction problem #Discrete mathematics #Graph #Markov Chains and Monte Carlo Methods #Mathematics #Random graph #Random regular graph #Replica #Stochastic processes and statistical mechanics #cond-mat.dis-nn #cond-mat.stat-mech #math.PR
paper · pdf · doi:10.1007/s10955-014-1136-2
published as J. Stat. Phys. 158, 300 (2015) · 45 pages, 24 figures, minor corrections in v2
arxiv created 2014/09/19 · openalex publication_date 2014/10/21 · arxiv updated 2015/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The bootstrap percolation (or threshold model) is a dynamic process modelling the propagation of an epidemic on a graph, where inactive vertices become active if their number of active neighbours reach some threshold. We study an optimization problem related to it, namely the determination of the minimal number of active sites in an initial configuration that leads to the activation of the whole graph under this dynamics, with and without a constraint on the time needed for the complete activation. This problem encompasses in special cases many extremal characteristics of graphs like their independence, decycling or domination number, and can also be seen as a packing problem of repulsive particles. We use the cavity method (including the effects of replica symmetry breaking), an heuristic technique of statistical mechanics many predictions of which have been confirmed rigorously in the recent years. We have obtained in this way several quantitative conjectures on the size of minimal contagious sets in large random regular graphs, the most striking being that 5-regular random graph with a threshold of activation of 3 (resp. 6-regular with threshold 4) have contagious sets containing a fraction 1/6 (resp. 1/4) of the total number of vertices. Equivalently these numbers are the minimal fraction of vertices that have to be removed from a 5-regular (resp. 6-regular) random graph to destroy its 3-core. We also investigated Survey Propagation like algorithmic procedures for solving this optimization problem on single instances of random regular graphs.