会议论文详细信息
ELC International Meeting on Inference, Computation, and Spin Glasses
The hard-core model on random graphs revisited
Barbier, Jean^1,2 ; Krzakala, Florent^1,2 ; Zdeborová, Lenka^3 ; Zhang, Pan^1,2,4
ESPCI, CNRS UMR 7083, 10 rue Vauquelin, Paris 75005, France^1
Laboratoire de Physique Statistique, CNRS UMR 8550, Ecole Normale Supérieure, Paris, France^2
Institut de Physique Théorique, IPhT, CNRS, 91191 Gif-sur-Yvette, France^3
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM, United States^4
关键词: Average degree;    Cavity method;    Hard-core repulsion;    Independent set;    Lattice modeling;    Random regular graph;    Structural glass;    Vertex Cover problems;   
Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/473/1/012021/pdf
DOI  :  10.1088/1742-6596/473/1/012021
来源: IOP
PDF
【 摘 要 】

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.

【 预 览 】
附件列表
Files Size Format View
The hard-core model on random graphs revisited 465KB PDF download
  文献评价指标  
  下载次数:28次 浏览次数:28次