Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold
Abstract
We study antiferromagnetic spin systems on random regular graphs through the lens of the phase transitions characterized by the complex zeros of the partition function. Our motivating examples include the hardcore model and the antiferromagnetic Potts model (including proper q-colorings at β=0). For both models on random d-regular graphs, we establish, with high probability over the graph, zero-free regions throughout the interior of the replica-symmetric regime. Asymptotically, this regime extends up to tree occupation density α< αRSB(d) = (2log d − 2loglog d + 2 − 2log 2 + od(1))/d for the hardcore model and up to degree d < dRSB(q) = (2q−1)log q − 2log 2 + oq(1) for proper q-colorings. Leveraging the standard algorithmic implications of zero-freeness, we obtain deterministic polynomial-time algorithms that multiplicatively approximate the corresponding partition functions at fixed rational parameters throughout this regime, with high probability over the graph. Our algorithmic guarantees significantly improve upon prior work and extend beyond the parameter ranges reached by previously known search algorithms. To establish our results, we first develop reinforced small subgraph conditioning, which resolves short-cycle fluctuations in the complex plane by lifting classical small subgraph conditioning on random regular graphs to random holomorphic functions. Second, we overcome the standard second-moment barrier caused by the exponential blowup of the bare second moment inside the replica-symmetric phase, by showing that replica symmetry implies a nonpositive Bethe functional and upgrading planted overlap concentration to an exponentially small bound, which enables a typical-graph truncation that controls complex second moments up to the replica symmetry breaking threshold.
Related
- Full replica symmetry breaking in the Sherrington-Kirkpatrick model
- Replica symmetry breaking at arbitrary depth
- Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
- Freeness of Arrangements with Regular Underlying Matroids
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
BibTeX
@misc{chen2026zerofreeness,
title = {{Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold}},
author = {Zejia Chen and Chunyang Wang and Xinyuan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40510},
eprint = {2610.40510},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40510},
}
RIS
TY - UNPB
TI - Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold
AU - Zejia Chen
AU - Chunyang Wang
AU - Xinyuan Zhang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40510
UR - https://arxiv.org/abs/2610.40510
AB - We study antiferromagnetic spin systems on random regular graphs through the lens of the phase transitions characterized by the complex zeros of the partition function. Our motivating examples include the hardcore model and the antiferromagnetic Potts model (including proper q-colorings at β=0). For both models on random d-regular graphs, we establish, with high probability over the graph, zero-free regions throughout the interior of the replica-symmetric regime. Asymptotically, this regime extends up to tree occupation density α< α_RSB(d) = (2log d − 2loglog d + 2 − 2log 2 + o_d(1))/d for the hardcore model and up to degree d < d_RSB(q) = (2q−1)log q − 2log 2 + o_q(1) for proper q-colorings. Leveraging the standard algorithmic implications of zero-freeness, we obtain deterministic polynomial-time algorithms that multiplicatively approximate the corresponding partition functions at fixed rational parameters throughout this regime, with high probability over the graph. Our algorithmic guarantees significantly improve upon prior work and extend beyond the parameter ranges reached by previously known search algorithms. To establish our results, we first develop reinforced small subgraph conditioning, which resolves short-cycle fluctuations in the complex plane by lifting classical small subgraph conditioning on random regular graphs to random holomorphic functions. Second, we overcome the standard second-moment barrier caused by the exponential blowup of the bare second moment inside the replica-symmetric phase, by showing that replica symmetry implies a nonpositive Bethe functional and upgrading planted overlap concentration to an exponentially small bound, which enables a typical-graph truncation that controls complex second moments up to the replica symmetry breaking threshold.
ER -