Degree-Free Spectral Independence for Log-Concave Holant Measures

For log-concave Holant measures with bounded insertion odds (γ≤θ_uv(i,j)≤Θ) and vertex thresholds b_v≤b, the authors prove a spectral independence bound of O(1+Θ+(b-1)T²) that does not grow with the maximum degree Δ. Previously Chen and Gu gave a bound of 2(P_max-1)≤2((1+r_max²λ_max)^Δ-1) on graphs of maximum degree Δ, which grows exponentially in Δ; this work replaces the Δ-dependence with dependence on the local parameters γ, Θ, and b. Theorem 4 states the general result, proved by combining an edge-to-vertex variance bound (Lemma 7) with a vertex variance bound (Lemma 6) via a Schur complement, with an alternative variance-maximization proof in Appendix A.

For the monomer–dimer model on every finite simple graph at any fixed activity λ>0, the measure is O((1+λ)²)-spectrally independent, and its Glauber dynamics satisfies t_rel=O_λ(m) and t_mix(ε)=O_λ(m(n log n+log(1/ε))). The bound holds after every feasible pinning and is independent of the maximum degree, answering the question raised by Chen, Liu, and Vigoda of improving the spectral independence bound beyond what is obtained by controlling total influence; on the infinite Δ-regular tree the total influence is Θ_λ(√Δ). Obtained directly from Theorem 4 with b=1 and γ=Θ=λ; the mixing-time statement is Corollary 5(i), whose proof in Appendix B uses the field dynamics comparison (Theorem 10) and an estimate of the smallest positive configuration probability.

For b-matchings with capacities 0≤b_v≤b at fugacity λ>0, the measure is C(1+λ)[1+λ+(b-1)max{1,λ^{2b}}]-spectrally independent with t_rel=O_{b,λ}(m); for uniform b-matchings (λ=1) this improves to Cb-spectral independence and t_rel=O(bm). Previously the spectral independence bound for uniform b-matchings was O_b(Δ^b) with mixing time O_Δ(n log n); this work removes the Δ-dependence and expresses the relaxation time linearly in the number of edges m. The spectral independence bounds follow by substituting γ=Θ=λ into Theorem 4; the relaxation and mixing times are given in Corollary 5(ii), derived in Appendix B from Theorem 10, Theorem 11, and two counting upper bounds on μ_min (2^m and (n+1)^{bn}).

The core technique controls the covariance of edge indicators by a diagonal matrix: a recursive coupling first yields a variance bound for occupied degrees that is independent of the maximum degree, and a harmonic surrogate K_e=φ_e(D_u,D_v) satisfying E[K_e|X_{-e}]=E[X_e|X_{-e}] then reduces edge variance to a diagonal term plus weighted vertex sums. In the recursive coupling, contributions of an alternating disagreement trail to occupied degrees cancel at internal vertices; this cancellation gives degree coupling independence and thereby bypasses the inherent degree dependence of total influence. Lemmas 6 and 7 provide the two variance bounds, Theorem 14 gives a spectral gap of at least 1-2r for block dynamics on occupied degrees, and the surrogate is constructed in Definition 17 via a backward recursion; explicit matching constants C_1=2+36λ and C_2=6 appear in Section 4.2.

The results concern log-concave Holant measures on finite simple graphs, requiring signatures that are log-concave, have no internal zeros, and satisfy f_v(0)>0, together with insertion odds in [γ,Θ] and vertex thresholds b_v≤b; under this setting the spectral independence and relaxation-time bounds are independent of the maximum degree for each fixed activity λ. The uniform b-matching bounds transfer to uniform b-edge covers via the complement map, with B=max{1,max_v(d_v-b_v)}. This provides directly citable complexity benchmarks for analyzing Glauber dynamics of monomer–dimer, b-matchings, and b-edge covers on unbounded-degree graphs.

This is a full-text reading, but formulas have been re-typeset in the text, so some inequality subscripts and constants (such as the explicit values of C_1, C_2, and A_⋆) are best confirmed against the original typesetting. Section 1.3 notes that in concurrent and independent work Chihao Zhang and Zihan Zhang also established a constant spectral independence bound for the monomer–dimer model on graphs of unbounded degree depending only on the activity; whether the constants and scope of the two routes agree is worth comparing later. Section 1.4 discloses the use of AI tools, including GPT-5.6 Sol, to develop the main proof ideas and edit the manuscript, with the authors stating responsibility for the mathematical content and final presentation; readers interested in proof details can cross-check the two independent proof routes given in the appendices.