Source-linked AI summary
Degree-Free Spectral Independence for Log-Concave Holant Measures
Xiaoyu Chen, Zejia Chen, Xinyuan Zhang
TL;DR
Existing total-influence bounds depend on maximum degree, even for monomer–dimer. This paper proves degree-independent spectral-independence bounds for log-concave Holant measures, using a covariance comparison through occupied degrees; it gives bounds for monomer–dimer and uniform b-matchings.
Problem
Total influence inherently depends on maximum degree, even for the monomer–dimer model.
Source: §1 · p. 3Method
The proof compares edge-indicator covariance with vertex-degree observables, using a Schur complement to connect their variance bounds.
Source: §1.1 · p. 4Results
C(1 + λ)^2 spectral independence holds for monomer–dimer, and uniform b-matchings are Cb-spectrally independent.
Source: §1 · p. 4Takeaways & Limitations
For monomer–dimer, the degree-independent bound answers a question posed by Chen, Liu, and Vigoda [CLV21, Section 8].
Source: §1 · p. 4The theorem assumes bounded vertex support and insertion odds satisfying γ ≤ θ_uv(i, j) ≤ Θ; its proof considers feasible residual instances.
Source: §1 · pp. 3–4, §4 · p. 12
Abstract
from arXiv · showhide
We establish a degree-independent bound on spectral independence for log-concave Holant problems on simple graphs. As a corollary, we obtain relaxation-time bounds for Glauber dynamics of $O_\lambda(m)$ for the monomer-dimer model at activity $\lambda$ and $O_{b,\lambda}(m)$ for $b$-matchings at fugacity $\lambda>0$, where $m$ is the number of edges. For uniform $b$-matchings, the relaxation-time bound improves to $O(bm)$. The main proof ideas were found using GPT-5.6 Sol.
1. Introduction
The introduction presents the goal of establishing degree-independent spectral independence for log-concave Holant measures without bounded total influence and situates it among existing approaches. It also outlines matching-model relaxation-time bounds and a proof strategy that decomposes edge variance into diagonal and vertex-degree contributions, then combines variance bounds using a Schur complement.
1. Introduction
- The Holant framework covers edge-state models with local vertex constraints, including monomer–dimer and b-matchings, and the paper focuses on log-concave local signatures.Glauber dynamics resamples one variable conditioned on the others; spectral independence uses influence bounds to derive rapid mixing through local-to-global arguments [ALO20].Source: §1 · pp. 2–3
1.2. Related work.
- For the monomer–dimer model, with b=1 and γ=Θ=λ, the spectral-independence bound holds after every feasible pinning and is independent of maximum degree for each fixed activity, improving the total-influence-controlled bound.Source: §1 · p. 4
1. Introduction
- Theorem 4 gives degree-independent spectral independence for simple-graph Holant measures with log-concave signatures, bounded vertex supports, and insertion odds bounded between γ and Θ.The bound holds after every feasible pinning and is independent of the graph and its maximum degree.Source: §1 · p. 4
- Oλ(m), O_b,λ(m), and O(bm) relaxation-time bounds follow for monomer–dimer, b-matchings, and uniform b-matchings, respectively.The monomer–dimer measure is also O((1 + λ)^2)-spectrally independent on every finite simple graph, after every feasible pinning.Source: §1 · p. 4
1.1. Proof overview.
- The proof bounds additive occupied-degree variance independently of maximum degree, reduces edge variance to diagonal and weighted vertex terms, and combines them through a covariance Schur complement.The degree-variance estimate follows from cancellation at internal vertices in the recursive coupling of Chen and Gu [CG24].Source: §1.1 · pp. 4–5
1.2. Related work.
- Prior work explored trickle-down spectral propagation, originating in local spectral expansion [Opp18] [ALOV19] and applied to sampling [ALO21] [WZZ24] [KOT26], and matrix-inverse methods.The matrix-inverse approach builds an exact or approximate inverse of the full correlation matrix from inverses of local matrices, reducing spectral analysis to local computations.Source: §1.2 · p. 7
1.3. Concurrent work.
- Concurrent independent work by Chihao Zhang and Zihan Zhang established a constant spectral-independence bound for monomer–dimer models on unbounded-degree graphs, depending only on activity.Source: §1.3 · p. 7
1.4. AI disclosure.
- The authors used AI tools, including GPT-5.6 Sol, to develop the main proof ideas and edit the manuscript, while retaining responsibility for its mathematical content and final presentation.Source: §1.4 · p. 7
2. Preliminaries
The preliminaries define finite Markov chains and Glauber dynamics, then connect covariance bounds for tilted conditional laws to spectral-gap bounds. They also state the assumptions for a field-dynamics comparison and a small-fugacity covariance result.
2.1. Basic Markov Chains.
- An ergodic finite Markov chain has a unique stationary distribution, and detailed balance with that distribution implies stationarity.For reversible chains, mixing can be bounded through the absolute spectral gap; the relaxation time is its reciprocal.Source: §2.1 · pp. 7–8
- Glauber dynamics selects an edge uniformly and resamples its occupancy conditionally, yielding a chain reversible with respect to the Holant measure.Its mixing time is defined by convergence in total variation from any initial distribution.Source: §2.1 · p. 8
2.2. Field dynamics.
- Field dynamics comparison turns covariance bounds for tilted conditional laws into a spectral-gap bound for Glauber dynamics.The stated comparison assumes a nonnegative function satisfying a condition for every feasible occupied set and 0 < η < 1; its integral must be finite.Source: §2.2 · pp. 8–9
- A prior result supplies a covariance bound for b-matching laws with vertex-dependent capacities when fugacity is between 0 and 1.The bound applies after every feasible occupied set.Source: §2.2 · p. 9
3. Spectral independence of occupied degrees
This section establishes degree coupling independence for log-concave Holant measures and uses coupling-based block dynamics to obtain spectral-independence and revealing estimates. The bounds apply after feasible degree pinnings and avoid a maximum-degree factor in the revealing estimate.
Degree coupling independence
- Degree coupling independence extends conditional laws to impossible pinnings while bounding expected discrepancy outside the changed coordinate by (C − 1)|k − ℓ|.For feasible pinnings, the extended law agrees with ordinary conditioning.Source: §3 · p. 9
- Log-concavity yields degree coupling independence with constant 2, including after feasible pinnings, via recursive couplings of adjacent degrees.The proof handles arbitrary supported degrees by adjoining low-activity pendant edges, gluing adjacent-degree couplings, and taking a limit.Source: §3 · pp. 9–10
Block dynamics
- When the retained random subset has maximum inclusion probability r, resampling the other degrees gives a block-dynamics spectral gap of at least 1 − 2r.The Dirichlet form of this chain is the left side of the stated variance inequality.Source: §3 · pp. 10–11
Spectral independence
- Choosing a uniformly random singleton yields 1-spectral independence in vertex coordinates, also after every feasible degree pinning.The conclusion follows from the variance inequality and the variance characterization of spectral independence.Source: §3 · p. 11
Application to Lemma 6
- The degree-variance argument bounds deviations from saturation using q_v, the probability that vertex v is not saturated.It uses 0 ≤ D_v ≤ b_v ≤ b to bound (D_v − b_v)^2 by b^2 times the indicator that D_v < b_v.Source: §3 · p. 11
Revealing estimate
- A quadratic revealing estimate covers edge functions of endpoint degrees on simple graphs without introducing a maximum-degree factor.Independent random vertex sampling makes cross terms vanish, including for edges sharing a vertex.Source: §3 · pp. 11–12
4. Edge-to-vertex variance bound
The section bounds edge variance through endpoint-degree surrogates, first matching each edge indicator’s conditional mean and then controlling the resulting star fluctuations. This yields the edge-to-vertex variance bound needed for spectral independence.
4. Edge-to-vertex variance bound
- For each edge, an endpoint-degree surrogate K_e matches X_e’s conditional mean given all other edge indicators, allowing variance control through vertex stars.The matching conditional means also yield the moment identities used to transfer the variance bound.Source: §4 · p. 13
- For matchings at activity λ, the argument gives O((1 + λ)^2) spectral independence.The matching proof uses the surrogate K_e and the variance identity in (4.2).Source: §4 · pp. 13–14
4.1. Harmonic surrogates.
- The harmonic surrogate is defined by a backward recursion and is uniformly bounded by L; when Θ ≤ 1, it lies between 0 and Θ.Its conditional mean equals that of X_e given X_{−e}.Source: §4.1 · p. 14
4.2. From star variances to edge variance.
- C1 = 3 + 113Θ + 1800(b − 1)T^2 and C2 = 6 give the edge-to-vertex variance bound in Lemma 7.The proof combines centered-star variance estimates and counts each edge in two vertex stars.Source: §4.2 · p. 15
4.3. Proof of the centered-star bound.
- The centered-star bound controls local fluctuations of the surrogates, separating boundary fluctuation from approximation error.For b = 1, the approximation error vanishes and the boundary estimate uses E[bK_e^2] ≤ Θp_e.Source: §4.3 · pp. 16–17
Appendix A. An alternative proof of the main theorem
The appendix gives an alternative proof of the main theorem by optimizing edge coefficients and applying the edge-to-vertex variance bound. It obtains a bound on the mean-normalized covariance quantity and then accounts for the variance weights used in spectral independence.
Appendix A. An alternative proof of the main theorem
- The mean-normalized quantity ρ is the local covariance quantity underlying spectral stability for field dynamics [CE22].Source: Appendix A · p. 20
- ρ ≤ C1 + √2C2b = O(1 + Θ + (b − 1)T^2) follows by applying Lemma 7 to the variance-maximizing edge weights.The weights maximize variance subject to their sum being 1.Source: Appendix A · p. 20
- The spectral-independence variance characterization costs at most a factor 1 + Θ beyond the bound on ρ.The insertion-odds bound gives (1 − p_e)^−1 ≤ 1 + Θ.Source: Appendix A · p. 20
Appendix B. Mixing-time bounds for matching models
The appendix applies covariance bounds to derive relaxation-time guarantees for monomer–dimer and b-matching dynamics. Uniform b-matchings receive the sharper O(bm) bound.
Appendix B. Mixing-time bounds for matching models
- The spectral-independence bounds specialize to O((1 + λ)^2) for monomer–dimer and to O(b) for uniform b-matchings.Source: Appendix B · p. 21
- O_{b,λ}(m) is the relaxation-time bound for b-matchings at fugacity λ > 0, while monomer–dimer has O_λ(m).The proof applies Theorem 10, using covariance bounds and a bound on the smallest positive configuration probability.Source: Appendix B · p. 21
- O(bm) is the relaxation-time bound for uniform b-matchings.For these matchings λ = 1 and A_{b,1} ≤ 1804b.Source: Appendix B · pp. 21–22
- For fixed λ > 0, the smallest positive b-matching configuration probability yields log(1/μ_min) = O_λ(min{m, bn log n}).The estimate uses bounds on the number of feasible configurations.Source: Appendix B · p. 22