Source-linked AI summary
Correlation Decay up to Uniqueness in Spin Systems
Liang Li, Pinyan Lu, Yitong Yin
TL;DR
For two-state anti-ferromagnetic systems, the paper addresses how to characterize strong spatial mixing and approximation on general graphs. It relates mixing on graphs of maximum degree at most Δ to uniqueness on regular trees up to Δ, and derives FPTAS guarantees, including for arbitrary graphs when uniqueness holds at all degrees.
Problem
The paper asks how to characterize strong spatial mixing on general graphs, a property that can support efficient partition-function approximation for two-state systems.
Source: §1 · p. 2, §1.1.1 · p. 4Method
The paper characterizes strong spatial mixing on bounded-degree graphs through uniqueness on infinite regular trees of every degree up to the bound.
Source: §1.1 · p. 3Results
Strong spatial mixing holds up to maximum degree Δ exactly under uniqueness on all infinite d-regular trees for d ≤ Δ, with an FPTAS under interior uniqueness and for arbitrary graphs when Δ = ∞.
Source: §1.1 · p. 3Takeaways & Limitations
Combined with ferromagnetic FPRAS and non-uniqueness hardness results, this gives an approximability classification for two-state systems except at the phase-transition boundary.
Source: §1.1 · p. 3The stated up-to-Δ uniqueness condition is defined for anti-ferromagnetic parameters and regular-tree degrees 1 ≤ d < Δ.
Source: §2.2 · p. 8
Abstract
from arXiv · showhide
We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most $\Delta$ if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to $\Delta$, where $\Delta$ can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most $\Delta$ when the uniqueness condition is satisfied on infinite regular trees of degree up to $\Delta$. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the hardness results of Sly-Sun and independently of Galanis-Stefankovic-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.
1 Introduction
The paper characterizes strong spatial mixing for two-state anti-ferromagnetic systems on general graphs through uniqueness on infinite regular trees, including bounded- and unbounded-degree settings. It derives approximation guarantees and explains why general systems require analysis beyond regular trees of the maximum degree.
1 Introduction
- Strong spatial mixing captures decay of correlations even with arbitrary fixed spins, and for two-state systems can lead to efficient partition-function approximation.The paper asks which systems have this property on arbitrary graph instances.Source: §1 · p. 2
1.1 Our results
- Strong spatial mixing holds on graphs of maximum degree at most Δ exactly when uniqueness holds on every infinite d-regular tree for d ≤ Δ.Under interior uniqueness on those trees, an FPTAS exists; the results include Δ = ∞.Source: §1.1 · p. 3
- Together with ferromagnetic FPRAS results and hardness under non-uniqueness, the approximation picture for two-state systems is classified except at the phase-transition boundary.Graphs of maximum degree at most 2 have polynomial-time exact partition-function computation.Source: §1.1 · p. 3
1.1.1 Regularity and monotonicity
- For general two-state systems, uniqueness on the maximum-degree regular tree need not imply uniqueness at lower degrees; the well-believed implication to all bounded-degree graphs holds only for monotone systems.The worst case may be a regular tree below the maximum degree, while faster decay at higher degrees can support unbounded-degree FPTAS results.Source: §1.1.1 · p. 4
1.2 Related works
- The paper develops a unified potential-based analysis on arbitrary trees; earlier work's analysis could not separate uniqueness by degree and therefore did not handle degree-bounded families.Prior correlation-decay approaches established results for the hardcore model and anti-ferromagnetic Ising model, among other settings.Source: §1.1.1 · p. 4, §1.2 · p. 6
1.1.2 Implications of the main results
- Threshold restatements extend prior tractable regions and yield FPTAS guarantees for arbitrary graphs in specified unbounded-degree uniqueness regimes.The results cover earlier anti-ferromagnetic algorithmic cases and previously uncovered settings.Source: §1.1.2 · pp. 4–5
2 Definitions and preliminaries
The preliminaries define two-state spin systems and their spatial-mixing properties, then express uniqueness on regular trees through a fixed-point condition. This tree condition is related to weak spatial mixing and is used to establish contraction.
2 Definitions and preliminaries
- A two-state model assigns binary spins to graph vertices, uses β and γ for edge weights and λ for vertex weights, and is anti-ferromagnetic when βγ < 1.Source: §2 · pp. 6–7
2.1 Correlation decay
- Strong spatial mixing measures how a change in fixed spins affects a vertex marginal as a function of the distance to the changed set; weak mixing measures distance to the fixed set.Source: §2.1 · p. 7
- The self-avoiding walk tree reduces marginal calculations on a graph with cycles to a tree, whose neighborhoods can be constructed in time proportional to their size.Source: §2.1 · pp. 7–8
2.2 The uniqueness condition
- Up-to-Δ uniqueness requires the fixed-point derivative magnitude to be below 1 for each relevant regular-tree degree, and is equivalent to weak spatial mixing on those trees.Under this condition, the derivative is bounded by an absolute constant c < 1.Source: §2.2 · p. 8
3 The strong spatial mixing on general graphs
For two-state anti-ferromagnetic systems, strong spatial mixing on graphs of maximum degree at most Δ is equivalent to uniqueness on infinite regular trees of degrees up to Δ. The proof controls correlation decay on irregular trees, and also yields a regular-tree result.
3 The strong spatial mixing on general graphs
- Strong spatial mixing on graphs of maximum degree at most Δ holds if and only if uniqueness holds on infinite d-regular trees for all d ≤ Δ.The result covers finite Δ and Δ = ∞.Source: §3 · pp. 8–9
- A potential function amortizes steps where the error does not decay, making the product of the error and potential contract at a constant rate.The analysis constructs upper and lower bounds for marginal ratios on arbitrary trees, then uses the self-avoiding walk tree to transfer decay to graphs.Source: §3 · pp. 9–10
- Up-to-Δ uniqueness bounds the contraction rate by a constant α < 1, which yields exponential decay with recursion depth.The contraction bound is the technical core of the proof.Source: §3 · p. 11
- On an infinite Δ-regular tree, uniqueness alone implies strong spatial mixing for two-state anti-ferromagnetic systems.This regular-tree result is a byproduct; for general systems it does not alone imply strong spatial mixing on all graphs of maximum degree at most Δ.Source: Strong spatial mixing on regular trees · p. 14
4 Algorithmic implications
The recursive correlation-decay procedure yields an FPTAS for the partition function under the corresponding uniqueness condition. For unbounded degrees, the analysis uses a refined depth and degree-dependent contraction to retain polynomial running time.
4 Algorithmic implications
- Up-to-Δ uniqueness yields an FPTAS for the partition function on graphs of maximum degree at most Δ, including arbitrary graphs when Δ = ∞.The result also holds for heterogeneous systems when each vertex's parameters satisfy the corresponding uniqueness condition.Source: §4 · pp. 14–16
- The partition function is reconstructed from a product of conditional probabilities, with each probability bounded away from zero.Approximating the marginals allows the product to be approximated within a factor of (1 ± nε).Source: §4 · p. 14
- For bounded maximum degree, truncating the self-avoiding walk tree at depth t gives an O(α^t) error and a polynomial-time marginal approximation when t is logarithmic in 1/ε.The marginal approximation is used to obtain the partition-function FPTAS.Source: §4 · pp. 14–15
- For unbounded degrees, computationally efficient correlation decay uses M-based depth and degree-dependent contraction to obtain a polynomial-time marginal approximation.The recursion's explored region has size at most n2M^ℓ, while the contraction decreases as degree grows.Source: §4 · pp. 15–16
5 Non-monotonicity of general two-state spin system
For general two-state anti-ferromagnetic systems, strong spatial mixing on an infinite d-regular tree need not imply strong spatial mixing on every graph of maximum degree at most d. The implication holds in a restricted parameter region, while non-monotone systems provide counterexamples beyond it.
5 Non-monotonicity of general two-state spin system
- Some two-state anti-ferromagnetic systems have strong spatial mixing on an infinite d-regular tree but not on all graphs of maximum degree at most d.The paper gives non-monotone systems as counterexamples to the general implication.Source: §5 · pp. 16–17
- The claimed general implication was previously associated with the regular tree as a worst case, but the counterexamples show that this does not extend to general two-state systems.The paper notes that the earlier claim holds only under limited settings.Source: §5 · p. 16
- When 0 ≤ β, γ ≤ 1, uniqueness on an infinite d-regular tree implies strong spatial mixing on trees of maximum degree at most d.In this parameter region, uniqueness on degree d also implies uniqueness on regular trees of smaller degree.Source: §5 · pp. 16–17
A The Uniqueness Thresholds
The section characterizes up-to-Δ uniqueness through critical thresholds in the interaction parameters, including how uniqueness varies with degree and when it can hold universally. It also bounds the degrees for which λ1(d + 1) can exceed λ2(d), showing that this inequality fails for all sufficiently large d.
A The Uniqueness Thresholds
- For every Δ, including infinity, up-to-Δ uniqueness is equivalent to γ∈(γc, 1/β); γc(β, λ, ∞)>1 and matches γc(β, λ, Δ) for some finite Δ.On sufficiently large-degree regular trees, uniqueness fails when γ≤1 and holds when γ>1.Source: A The Uniqueness Thresholds · pp. 20, 22, 23
- When β=0, up-to-Δ uniqueness holds exactly for λ∈(0, λc(γ, Δ)); universal uniqueness occurs exactly when γ>1 and λ∈(0, λc(γ)).The threshold λc(γ, Δ) is defined as a minimum over degrees; for γ≤1 the universal-uniqueness threshold collapses to zero.Source: A The Uniqueness Thresholds · pp. 20, 25
- For γ ≤ 1, (β, γ, λ) is up-to-∆unique exactly when λ ∈ (0, λc) ∪ (λ̄c, ∞); when β = γ, λc·λ̄c = 1, so uniqueness is equivalent to |log λ| > log λ̄c.Source: A The Uniqueness Thresholds · p. 20
- For general anti-ferromagnetic systems, universal uniqueness is possible only when γ>1, with a finite positive lower bound on λ sufficient and an upper bound necessary.For γ>1, the section establishes a finite positive threshold for uniqueness across all degrees.Source: A The Uniqueness Thresholds · pp. 20, 26
- For γ>1, the λ-uniqueness regime can have three intervals, so the earlier two-interval simplification applies only when both β and γ are at most 1.The paper notes that this correction does not affect its main results, since the threshold lemma is used for interpretation and comparison rather than their proofs.Source: A The Uniqueness Thresholds · p. 21
- For d ≥ d0(β, γ), λ1(d + 1) ≤ λ2(d); any degree with λ1(d + 1) > λ2(d) must satisfy d < log_{1/(βγ)}(81γ).The finite cutoff d0(β, γ) bounds the degrees at which the strict inequality can hold.Source: A The Uniqueness Thresholds · p. 28
B Proof of Lemma 11 (a Mean Value Theorem approach)
The proof uses mean-value identities to track transformed errors and bounds those errors under the stated parameter or degree conditions.
B Proof of Lemma 11 (a Mean Value Theorem approach)
- The Mean Value Theorem expresses the transformed error as ϕ′(eR)·δv for some eR between Rv and Rv + δv.The proof also applies the theorem to differences formed from the child inputs.Source: B Proof of Lemma 11 (a Mean Value… · p. 29
- For v ∉ Λ, the proof bounds δv by Rv + δv and then by f(0, ..., 0) = λ.The passage also gives Rv + δv ≤ λ under its stated condition.Source: B Proof of Lemma 11 (a Mean Value… · p. 29
- When γ > 1 or k is bounded, the proof concludes that ǫv = O(1).The argument uses boundedness of the relevant degree-dependent term when γ > 1, or d ≤ k when k is bounded.Source: B Proof of Lemma 11 (a Mean Value… · p. 29
- The proof defines transformed values yv = ϕ(Rv) and yvi = ϕ(Rvi), then applies the Mean Value Theorem to intermediate child values.The transformed parent value is written as yv + ǫv = ϕ(f(ϕ−1(yv1), ..., ϕ−1(yvd))).Source: B Proof of Lemma 11 (a Mean Value… · pp. 29–30
C Finding a good potential function heuristically
The authors describe a heuristic for finding a potential function, starting from a necessary condition at the uniqueness boundary and extending it to a differential equation. They explicitly state that this heuristic is not needed for the result’s soundness.
C Finding a good potential function heuristically
- The authors call the discovery heuristic non-rigorous and logically unnecessary for proving their result’s soundness.They present it as a general approach that may be useful in other scenarios.Source: C Finding a good potential function… · p. 30
- The heuristic has three steps: find a necessary condition, extend it across the variable range, then solve the resulting differential equation.The extension is explicitly identified as a heuristic step.Source: C Finding a good potential function… · p. 30
- The heuristic assumes the system is at the uniqueness boundary, where x̂ = f(x̂) is the positive fixed point.The passage says identities for this fixed point are then used.Source: C Finding a good potential function… · p. 30
- The potential is sought so α(x) = |f′(x)|Φ(f(x)) is maximized at x̂, yielding α′(x̂) = 0.The derivation uses x̂ = f(x̂) and f′(x̂) = −1.Source: C Finding a good potential function… · p. 31
- Extending the condition to all x gives a differential equation whose solution supplies the potential function used in the paper.The authors note that potential-function analysis has no standard routine for selecting such a form.Source: C Finding a good potential function… · pp. 30–32
- A different fixed-point identity yields the potential function used in.The authors note that the choice of which identity to extend heuristically can affect the resulting potential.Source: C Finding a good potential function… · p. 32