Zero-freeness proved for antiferromagnetic models on random regular graphs
Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold
Data Structures and Algorithms
Summary
This paper deals with mathematical models used to study systems where elements repel each other, such as certain coloring problems or particle arrangements on networks. The authors show that the mathematical functions describing these systems do not have problematic zeros within a broad range of parameters, which helps us understand the behavior of these systems more reliably. They also use this insight to create faster algorithms that can approximate important quantities for large random networks. Their methods work well up to a known theoretical boundary where the system's behavior becomes more complex.
What this means in practice
- •For algorithm developers: Create efficient polynomial-time algorithms for approximating complex partition functions in antiferromagnetic models on random regular graphs.
- •For network modelers: Improve understanding and simulation of repulsive interactions on large random networks by using zero-freeness insights up to the replica symmetry breaking threshold.
Authors
Zejia Chen, Chunyang Wang, Xinyuan Zhang
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 $$α< α_{\mathrm{RSB}}(d) = (2\log d - 2\log\log d + 2 - 2\log 2 + o_d(1))/d$$ for the hardcore model and up to degree $$d < d_{\mathrm{RSB}}(q) = (2q-1)\log q - 2\log 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.