2000/11/30 by Martin Weigt, Alexander K. Hartmann · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Graph #Hard spheres #Lattice (music) #Mathematics #Physics #Quantum mechanics #Random graph #Replica #Statistical mechanics #Statistical physics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Topological and Geometric Data Analysis #Vertex (graph theory) #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.63.056127
published as Phys. Rev. E 63, 056127 (2001) · 32 pages, 9 eps figures, to app. in PRE (01 May 2001)
arxiv created 2001/02/19 · openalex publication_date 2001/04/26 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The minimal vertex-cover (or maximal independent-set) problem is studied on random graphs of finite connectivity. Analytical results are obtained by a mapping to a lattice gas of hard spheres of (chemical) radius 1, and they are found to be in excellent agreement with numerical simulations. We give a detailed description of the replica-symmetric phase, including the size and entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c approximately 1.43. The replica-symmetric solution breaks down at c=e approximately 2.72. We give a simple one-step replica-symmetry-broken solution, and discuss the problems in the interpretation and generalization of this solution.