CS Paper Radar

Coupling Independence Implies Zero-Freeness

Shuai Shao, Ke Shi

cs.DS math-phmath.PR ·submitted 2026-10-08 17:59 UTC · v1
theory

Abstract

For $Δ\ge2$ and $q\ge11Δ/6$, we prove that the antiferromagnetic $q$-state Potts partition function on finite simple graphs of maximum degree at most $Δ$ has no Fisher zeros in a graph-uniform complex neighbourhood of $[0,1]$. For $q>11Δ/6$, the proof establishes coupling independence throughout $[0,1]$ using a soft version of Vigoda's flip dynamics. Our main tool is a separator-shell transfer theorem for the Potts model on induced-subgraph closed classes of graphs of maximum degree at most $Δ$, with $q\geΔ+1$. It yields a graph-uniform zero-free neighbourhood of $[0,1]$ from Hamming coupling independence at $0$ and a uniform coupling-independence bound on each interval $[δ,1]$, $δ\in(0,1]$. We also obtain zero-free Lee-Yang polydiscs around the uniform field for vertex- and edge-colour fields. For Boolean Holant problems on bounded-degree graphs whose signatures come from a fixed finite family of log-concave symmetric signatures $f$ with $f(0)>0$, such as $b$-matchings, we obtain graph-uniform zero-free polytubes around every bounded box of nonnegative activities; their union is an open zero-free neighbourhood of the nonnegative orthant. An appendix summarizes further coupling-independence inputs and the zero-free regions they yield.

Comment
40 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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.68
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

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs

cs.DS math.PR ·2026-09-11 ·Zhidan Li, Kuan Yang
similarity 0.62
Abstract · A revised version

We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. Under the same condition, we also give a deterministic fully polynomial-time approximation scheme (\textbf{FPTAS}) for the partition function. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).

0.26

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.59
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

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More)

cs.CC cs.DMcs.DSmath.CO ·2026-09-10 ·Édouard Bonnet, Yeonsu Chang
similarity 0.59
Abstract · 34 pages, 11 figures

We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the $5 \times 5$ grid as an induced minor. This negatively answers a question of Dallard--Milanič--Štorgel that has attracted sustained attention, and refutes a conjecture by Gartland and Lokshtanov. Unless $N$-variable 3-SAT can be solved in time $2^{\mathcal O(N^{1-\varepsilon})}$ for some $\varepsilon > 0$, MIS requires $2^{Ω(n^{1/2-o(1)})}$ time on $n$-vertex graphs in this class. This complements a $2^{\widetilde{O}(n^{2/3})}$-time algorithm on any $H$-induced-minor-free class by Korhonen and Lokshtanov. Exploiting a connection between low twin-width or reduced parameters on one hand and planar-induced-minor-freeness on the other, we further show that 3-Coloring, Feedback Vertex Set and Dominating Set are NP-complete on weakly sparse graphs of reduced component max-leaf (hence twin-width) at most 3, even when a witnessing contraction sequence is given. Classes of bounded reduced component max-leaf (by any constant) and of twin-width at most 3 are known to exclude a fixed planar graph as an induced minor. The 3-Coloring and Feedback Vertex Set results refute more cases of the Gartland--Lokshtanov conjecture, even when the inputs are weakly sparse. The complexity of MIS in weakly sparse graphs excluding a planar induced minor remains open.

0.48

Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

cs.DS ·2026-09-30 ·Pan Peng, Kefan Yu
theory similarity 0.59
Abstract

We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial in $1/\varepsilon$ and independent of the number $n$ of vertices. Previously, the best bound known for this problem was the $\operatorname{poly}(\log n)$-query guarantee that follows from the general outerplanar-graph tester of Babu, Khoury, and Newman (2016) in the stronger $\textit{adjacency-list model}$, which provides exact degree queries and indexed access to neighbors. Our tester has $\textit{two-sided error}$, which is necessary in general: induced-$P_3$-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.

0.16

Flip-packability: uniform characterisations of tame graph classes

cs.LO cs.DMmath.COmath.LO ·2026-09-27 ·Ioannis Eleftheriadis
theory similarity 0.57
Abstract · 32 pages; added funding information

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.

0.24

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

cs.CC ·2026-11-05 ·Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
theory similarity 0.57
Abstract

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

0.23

On the Critical Window for Adaptable 2-Colorability

cs.DM math.CO ·2026-09-10 ·Thomas Snow
theory similarity 0.57
Abstract · 37 pages; typo corrected in reference

We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erd$ő$s-R$é$nyi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on $O(\log{n})$ many vertices.

0.21