The hard-core model on random graphs revisited
arXiv:1306.4121 · doi:10.1088/1742-6596/473/1/012021
Abstract
We revisit the classical hard-core model, also known as independent set and dual to vertex cover problem, where one puts particles with a first-neighbor hard-core repulsion on the vertices of a random graph. Although the case of random graphs with small and very large average degrees respectively are quite well understood, they yield qualitatively different results and our aim here is to reconciliate these two cases. We revisit results that can be obtained using the (heuristic) cavity method and show that it provides a closed-form conjecture for the exact density of the densest packing on random regular graphs with degree K>=20, and that for K>16 the nature of the phase transition is the same as for large K. This also shows that the hard-code model is the simplest mean-field lattice model for structural glasses and jamming.
arXiv comment9 pages, 2 figures, International Meeting on "Inference, Computation, and Spin Glasses" (ICSG2013), Sapporo, Japan
References in corpus (18)
- Theoretical perspective on the glass transition and amorphous materials
- Mean field theory of hard sphere glasses and jamming
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Lattice Glass Models
- Glass models on Bethe lattices
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Replica bounds for diluted non-Poissonian spin systems
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- Message passing for vertex covers
- Potts Glass on Random Graphs
- Statistical mechanics of the vertex-cover problem
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- Glassy phases in Random Heteropolymers with correlated sequences
Cited by in corpus (19)
- Statistical physics of inference: Thresholds and algorithms
- Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
- On independent sets in random graphs
- Minimal contagious sets in random regular graphs
- Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
- Learning from Survey Propagation: a Neural Network for MAX-E--SAT
- Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
- Spin systems on Bethe lattices
- Parallel Tempering for the planted clique problem
- Solution space structure of random constraint satisfaction problems with growing domains
- Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
- Spin glass phase transitions in the random feedback vertex set problem
- The asymptotics of the clustering transition for random constraint satisfaction problems
- Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
- Typical Performance of Approximation Algorithms for NP-hard Problems
- High-density hard-core model on triangular and hexagonal lattices
- Percolation with small clusters on random graphs
- High-density hard-core model on and norm equations in ring
- Decomposing random regular graphs into stars