CS Paper Radar

A general framework for crystallization in maximal hard-core models

Alexander Barg, Qidong He, Geyang Wang

cs.IT cond-mat.stat-mechmath-phmath.PR ·submitted 2026-10-08 00:53 UTC · v1
unusual

Abstract

We study general maximal hard-core models on periodic lattice-type graphs. While for standard models, phase coexistence may arise for high activity, for maximal models this behavior may occur also for sufficiently low activity values. Relying on the concept of volume allocation, we develop a {\em unified set of assumptions} that imply the Peierls condition, a convergent cluster expansion for the partition function, and hence the conclusions of Pirogov-Sinai theory for this class of models. We further check these assumptions for a number of examples including standard lattice-type periodic graphs, proving crystallization for both high and low activity. We also derive estimates for the values of activity that bound the phase coexistence regions in the phase diagram, rewriting for this purpose the proof of a technical result in the derivation of Pirogov-Sinai theory.

Comment
33pages, 11 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Low-Temperature Sampling via Equilibrium Disagreements

cs.DM cs.DSmath.PR ·2026-11-05 ·Andreas Galanis, Daniel Stefankovic
similarity 0.53
Abstract · Abstract shortened to fit arXiv requirements

We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: --- For the hard-core model on random bipartite $d$-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the non-uniqueness regime $λ>λ_c(d)$. --- For the random-cluster model on random $d$-regular graphs, for every real $q>2$, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in $n^{3/2+o(1)}$ steps for all $β\geq β_c$. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in $n^{3/2+o(1)}$ steps for $β\leq β_c$. --- For the ferromagnetic Ising model on random $d$-regular graphs, Glauber dynamics initialised from all-plus or all-minus mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the low-temperature regime $β>β_c(d)$. We also give an $n^{2+o(1)}$-time algorithm that combines phase samples into samples from the full distribution, avoiding in particular time-costly approximations of the corresponding partition functions to the target sampling accuracy.

0.17

Near linear mixing of random-cluster Glauber dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-11-04 ·Zhangsong Li
similarity 0.52
Abstract · 37 pages

We study the random-cluster model on locally treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability $p \in (0,1)$ and a clustering weight $q \in [1,\infty)$, generalizing independent Bernoulli percolation ($q=1$) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer $q$. For $q>2$, at parameter $p$ below the tree uniqueness threshold $p_{\mathsf u}(q,d)$, it is expected that sampling is easy and local Markov chains mix rapidly on all graphs with degree bounded by $d$. On typical graphs, the same is predicted at $p>p_{\mathsf s}(q,d)$, where $p_{\mathsf s}(q,d)$ is a second uniqueness transition point on the $d$-regular wired tree. Our result confirms this prediction for random regular graphs, showing that the random-cluster Glauber dynamics mix in time $O(n^{1+o(1)})$ on a random $d$-regular graph for all fixed $q>2$ and $p>p_{\mathsf s}$. For comparison, the best prior sampling results for these models that held for all $p>p_{\mathsf s}$ required $q\gtrsim \log d$ \cite{BGPZ26}. The key difficulty is that simply utilizing the contraction of cavity messages on $d$-regular trees does not suffice to cover the entire regime $q>2$. To address this issue, motivated by \cite{LS26}, we develop a careful bootstrap argument to show the shrinkage of disagreement under grand coupling. The core ideas of the proof were generated using GPT-6 and the Pharos system; the proof was then refined and simplified by the author.

0.10

Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold

cs.DS math-phmath.PR ·2026-10-29 ·Zejia Chen, Chunyang Wang, Xinyuan Zhang
similarity 0.52
Abstract · Revised and expanded: strengthened the characterization of the replica-symmetric phase, reorganized and expanded the proofs. 84 pages

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. As a key intermediate step, we establish the pointwise equivalence, away from the threshold, of three notions of replica symmetry: geometric (averaged pairwise correlation decay), thermodynamic (convergence to the Bethe free-energy prediction), and variational (nonpositivity of the Bethe functional). To establish zero-freeness, we develop reinforced small subgraph conditioning, lifting classical small subgraph conditioning to random holomorphic functions to control short-cycle fluctuations. We also use variational replica symmetry to obtain exponential planted overlap concentration. This enables a typical-graph truncation that controls complex second moments up to the replica symmetry breaking threshold.

0.28

Rapid mixing of Potts Glauber dynamics throughout uniqueness

cs.DM math.PRmath-ph ·2026-10-30 ·Antonio Blanca, Reza Gheissari, Heehyun Park, Xusheng Zhang
hot direction similarity 0.51
Abstract

Sampling from the ferromagnetic $q$-state Potts model is a fundamental problem in statistical physics and approximate counting. Although computationally hard in the worst case, sampling is expected to be efficient throughout the high-temperature uniqueness regime of the model using the natural single-site Glauber dynamics. We establish fast mixing bounds for every $q$, in the full high-temperature regimes in the two central graph families on $n$ vertices. (1) For every $Δ\ge 3$, the Potts Glauber dynamics mixes in $n\operatorname{polylog}(n)$ steps with high probability on a uniformly random $Δ$-regular graph for all $β<β_u(q,\mathbb T_Δ)$ where $β_u(q,\mathbb T_Δ)$ is the uniqueness threshold on the $Δ$-regular tree; (2) For every $d\ge 2$, the Potts Glauber dynamics has inverse spectral gap $n^{1+o(1)}$ on cubes or tori in $\mathbb Z^d$ for all $β<β_c(q,\mathbb Z^d)$ where $β_c(q,\mathbb Z^d)$ is the critical point on $\mathbb Z^d$. Both temperature thresholds are sharp as the Glauber dynamics slows down exponentially above them. These results overcome the challenge of bounding mixing times without access to correlation decay bounds in the presence of pinnings (i.e., without spectral independence or strong spatial mixing). For this purpose, our proof introduces a new dichotomy principle: throughout the high-temperature regime, any initial spin distribution is either such that its pinnings ensure good correlation decay, or Glauber dynamics escapes from that distribution quickly. We expect this kind of dichotomy to have further applications. As a demonstration, we also develop its analog for random-cluster dynamics and use it to prove that Swendsen-Wang dynamics on random $Δ$-regular graphs mixes in $O(\log n)$ time throughout uniqueness. The results in this paper were arrived at with the assistance of ChatGPT 5.6 and 6.

0.23

Lee-Yang theorem for fermions

cs.CC quant-phcond-mat.stat-mechcond-mat.str-el+1 ·2026-09-20 ·Chaithanya Rayudu, Takahiro Misawa, Andrew Zhao, Jun Takahashi
theory similarity 0.50
Abstract · 21 pages. v2: extended the class of fermionic Lee-Yang Hamiltonians

Lee-Yang theorems are a powerful tool for studying many-body systems, with applications ranging from analyzing phase transitions to proving the efficiency of certain classical and quantum algorithms. In this work, we prove a Lee-Yang zero-freeness theorem for the partition function of a broad class of interacting fermion models, implying the existence of a provably efficient quantum algorithm for estimating their ground-state energies. This class includes several well-known models such as the attractive Hubbard model, repulsive Hubbard model on bipartite graphs, and the interacting Hofstadter model. Our results also rigorously establish the nonexistence of phase transitions in these models in the presence of a nonzero local external field.

0.45

An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs

cs.DS math.PR ·2026-08-19 ·Zhidan Li, Kuan Yang
similarity 0.49
Abstract

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

0.18

Absence of critical scaling in the Schelling segregation model

cs.GT cond-mat.stat-mechcs.MA ·2026-08-17 ·Mouhssine Rifaki
theoryunusual similarity 0.49
Abstract · 24 pages, 16 figures, 6 appendices. Over 12,500 simulation runs on periodic grids up to L = 320; Chebyshev radii r_0 up to 6 (k = 168 neighb…

We find no evidence of critical scaling in the Schelling segregation model, in either the Moore neighborhood or its dense-spectrum extension to Chebyshev radii up to $r_0 = 6$ ($k = 168$ neighbors). On periodic grids up to $L = 320$ with 50 trials per point (> 12,500 runs), every finite-size scaling diagnostic in the Moore baseline fails: the per-$L$ $T_c$ does not drift, Var$(S) \sim L^{-2.02 \pm 0.09}$ matches trivial averaging, $γ/ν\approx 0$, and the scaling collapse never reaches a finite optimum. The 8-site Moore neighborhood restricts satisfaction to ratios $j/k$ with $k \leq 8$, giving $S(T)$ a staircase structure with 23 rational thresholds; discreteness alone does not forbid criticality (cf. the Ising model), but the scaling evidence rules it out empirically. A branching-ratio calculation predicts subcritical cascades of mean size $1/(1-R)$ and is validated by perturbation experiments to within 15%; the multiscalar dissimilarity length stays finite across the transition. The dense-spectrum extension strengthens the negative verdict: across $r_0 \in {3,4,5,6}$ on $L \in {40,80,160}$ the Binder cumulant has no $L$-curve crossing and the per-$L$ $T_c$ drift is monotonic and unsaturated; at $r_0 = 4$, extending to $L = 320$ gives $α= -2.70$, below the critical boundary $α= -2$, dissolving an apparent $α= +0.81$ signal visible only on $L \in {40,80}$. The mechanism is the absence of long-range correlation in equilibrium plus deterministic high-$k$ dynamics, not the staircase structure. With a Beta-distributed heterogeneous tolerance, the intolerant tail drives segregation even at moderate population-average tolerance. The staircase theorem and cascade mechanism together account for the Schelling transition without invoking critical phenomena.

0.31

Improved rapid phase ordering for Ising dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-10-20 ·Zhangsong Li, Allan Sly
similarity 0.48
Abstract · 59 pages, 3 figures

We study Glauber dynamics for the Ising model on random $d$-regular graphs with $n$ vertices at low temperature, in the regime $β\geq C/d$ where $C,d$ are sufficiently large constants. In this regime, the full mixing time is exponential in $n$, because of the bottleneck between the two dominant phases: configurations with a majority of plus spins and configurations with a majority of minus spins. We show that, for sufficiently large $d$, if the dynamics is initialized with an excess of at least $ε_{C,d} n$ plus spins over minus spins, then it quasi-equilibrates in time $O(\log n)$ to the Gibbs measure conditioned on positive magnetization. In addition, the required bias $ε_{C,d}$ can be chosen so that $ε_{C,d}\to 0$ as $d,C\to\infty$. Previous bound of \cite{GSS25+} in the Ising and large-$d$ setting required $β\gtrsim (\log d)/d$. A key difficulty is that, even from the all-plus initialization, one must control the propagation of negative information in spacetime in a low-temperature model with strong local correlations. We address this by developing a new bootstrap approach to proving subcriticality of disagreement clusters under the grand coupling.

0.32