Improved replica bounds for the independence ratio of random regular graphs

DOI10.1007/s10955-022-03062-7OpenAlexW4318350627MaRDI QIDQ2687694

Viktor Harangi

Publication date: 7 March 2023

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.01353

zbMATH Keywords

random regular graphsindependent setshard-core modelreplica symmetry breaking

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• A hierarchical version of the de Finetti and Aldous-Hoover representations
• On the independence and chromatic numbers of random regular graphs
• Local algorithms, regular graphs of large girth, and random regular graphs
• Replica bounds by combinatorial interpolation for diluted spin systems
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• Spin systems on Bethe lattices
• Local algorithms for independent sets are half-optimal
• The Parisi formula has a unique minimizer
• Maximum independent sets on random regular graphs
• The Parisi formula
• Lower bounds on the chromatic number of random graphs
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Fractional colorings of cubic graphs with large girth
• Induced Forests in Regular Graphs with Large Girth
• The Independence Ratio of Regular Graphs
• The Sherrington-Kirkpatrick Model
• Replica bounds for diluted non-Poissonian spin systems
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

This page was built for publication: Improved replica bounds for the independence ratio of random regular graphs