The hard-core model on random graphs revisited

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.

9 pages, 2 figures, International Meeting on "Inference, Computation, and Spin Glasses" (ICSG2013), Sapporo, Japan

References in corpus (7)

• Theoretical perspective on the glass transition and amorphous materials
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Message passing for vertex covers
• Potts Glass on Random Graphs
• Statistical Mechanics of the Hyper Vertex Cover Problem

Cited by in corpus (18)

• Statistical physics of inference: Thresholds and algorithms
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• 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-$3$-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 ${\mathbb{Z}}^2$ and norm equations in ring $\mathbb{Z}[\sqrt[6]{-1}]$
• Decomposing random regular graphs into stars