Further Potts Zero-Free Regions from Coupling Independence

Shuai Shaoshao10@ustc.edu.cnKe Shiself.ke.shi@gmail.com

School of Computer Science and Technology, University of Science and Technology of China.

Abstract

The main article [SS26] establishes a transfer principle turning Hamming coupling independence of the antiferromagnetic Potts model into graph-uniform zero-free neighbourhoods of activity intervals, and proves coupling independence above the Vigoda threshold q>11\Deg/6. The present companion article proves coupling independence in seven further regimes — near-Vigoda, Carlson–Vigoda, large-girth, high-temperature, BBR-interval, edge-Potts, and girth-five — and records, through the same transfer principle, the resulting zero-free neighbourhoods for all normalized pinned partition functions.

AI Disclosure. The coupling-independence proofs in this article were produced by AI models — GPT-5.6 Sol, except the girth-five results, which were proved by GPT-6 Astra. A Lean formalization, developed with assistance from GPT-6 Astra and Claude Opus 5.5, proves every numbered theorem, lemma, proposition and corollary of this article, some in an equivalent form [Shi26]. The Lean statements take only the displayed mathematical hypotheses. It also proves, in the form the proofs use, the results cited in the large-girth, BBR-interval, and girth-five regimes, [CLMM23, Lemmas 5.13 and 8.7 and Equation (10)] and [BBR25, Proposition 2.6(i) and Theorem 2.5], with Proposition 2.6(i) also for \Deg\ge q+2. At the twenty critical pairs (\Deg,q)=(6j,11j), 1\le j\le20, in place of [CFG+25, Theorem 20] it extends the Carlson–Vigoda contraction of Theorem 5.1 to q\ge11\Deg/6 for every \Deg\ge6. The authors assume responsibility for all claims.

1Introduction

The main article [SS26] proves that on any induced-subgraph-closed class of graphs of maximum degree at most \Deg with q\ge\Deg+1, Hamming coupling independence at x=0 together with a uniform coupling bound on each [\delta,1], \delta>0, yields a graph-uniform zero-free neighbourhood of [0,1] for all normalized pinned Potts partition functions (Theorem 2.4 below). This article supplies the coupling input in seven further regimes; Table 1 lists the resulting zero-free regions, and Section 4 states them precisely.

Regime	Parameters	Zero-free near
near-Vigoda	\Deg\ge2, q\ge(11/6-1/84000)\Deg	[0,1]
Carlson–Vigoda	\Deg\ge125, q\ge1.809\Deg	[0,1]
large-girth	\Deg\ge3, q\ge\Deg+3; \operatorname{girth}(G^\tau)\ge g_*(q,\Deg)	[0,1]
high-temperature	\Deg\ge2, q>\frac{11}{6}(1-x_)\Deg, x_\in(0,1]	[x_*,1]
BBR interval	q\ge3, \Deg/q\ge(e-1/2)/(e-1); \operatorname{girth}(G^\tau)\ge g_{\rm BBR}(q,\Deg)	[x_0,1]
edge-Potts	\Deg\ge2, q\ge3\Deg	[0,1]
girth-five	q\ge(1+\delta)\Deg, 0<\delta\le1; \Deg\ge\Deg_5(\delta), \operatorname{girth}(G^\tau)\ge5	[0,1]

In every row the conclusion is \nZpin{G}{\tau}(z)\ne0 for all z in an \eps-neighbourhood of the stated interval, with \eps>0 depending only on the listed parameters, uniformly over graphs and pinnings; the unnormalized pinned polynomial has no zeros in the same neighbourhood except possibly at z=0, of order m_G(\tau). In the edge-Potts row the polynomial is \nZpin{L(G)}{\tau}, with \tau an edge-colour pinning, and m_G(\tau) is replaced by m_{L(G)}(\tau). In the BBR row, x_0:=1-\frac q\Deg\bigl(1-\frac k\Deg\bigr)^{\!2} \frac{\Deg-k}{\Deg-k/2} with k:=e\frac{\Deg-q/2}{\Deg-q} (and x_0:=3/4 if (q,\Deg)=(3,4)). The girth-five row assumes no bounds on local short-cycle counts.

Table 1. Zero-free regions proved in this article.

The coupling input of each row originates as follows: near-Vigoda, the strict flip coupling of [SS26] continued across the critical line, with [CFG+25, Theorem 20] at the critical pairs (\Deg,q)=(6j,11j); Carlson–Vigoda, the contraction of [CV25] extended to x\in[0,1]; large-girth, the mechanism of [CLMM23] extended to x\in[0,1]; high-temperature, Proposition 3.2; BBR, the certificate of [BBR25] at large girth; edge-Potts, a slot-lift coupling after [CWZZ25]; girth-five, a covariance recursion built on an all-pinning spectral gap proved in Section 9.2, converted to a coupling by the sphere-to-coupling theorem of [CLMM23, Lemma 5.13]; the girth-five setting parallels the spectral local-to-global framework of [CL26], from which no input is taken.

Organization. Section 2 fixes the pinning framework and recalls the transfer principle from the main article. Section 3 recalls the strict Vigoda-threshold coupling results and the soft-flip interface used throughout. The remaining sections prove the seven regimes in turn.

2Framework

This section fixes the notation of [SS26] and recalls the transfer principle used in every subsequent section.

2.1Pinnings and partition functions

Throughout, q and \Deg are positive integers, \colours=\{1,\ldots,q\}, x\in[0,1] is a real base point, and z\in\C is the complex edge-activity variable. We write \one{A} for the indicator of an event A, and use the convention 0^0=1. For a finite graph G, write

\Delta(G):=\max_{v\in V(G)}\deg_G(v)

for its maximum degree; the symbol \Deg denotes a fixed degree bound. Let

\Gdeg:=\set{G:\text{$G$ is finite, simple, and }\Delta(G)\le\Deg},

and, for g\ge3, let

\Gdegg{g}:=\set{G\in\Gdeg:\operatorname{girth}(G)\ge g}.

Both classes are closed under induced subgraphs. We use the convention that an acyclic graph, including the empty graph, has girth +\infty.

Fix G=(V,E)\in\Gdeg. For a pinning \tau\colon\Lambda\to\colours, write

V^\tau:=V\setminus\Lambda, \qquad G^\tau:=G[V^\tau],

and call G^\tau the free graph. For u\in V^\tau and c\in\colours, define the boundary count

\bcount_u^\tau(c) :=\abs{\set{p\in\Lambda:up\in E,\ \tau_p=c}}. \tag{1}

Boundary counts record pinned neighbours separately, even when several have the same colour. The normalized pinned partition function has the factorized form

\nZpin{G}{\tau}(z) =\sum_{\varphi\colon V^\tau\to\colours} \prod_{u\in V^\tau}z^{\bcount_u^\tau(\varphi_u)} \prod_{uv\in E(G^\tau)} \bigl(z\one{\varphi_u=\varphi_v}+\one{\varphi_u\ne\varphi_v}\bigr). \tag{2}

Writing m_G(\tau) for the number of monochromatic edges of G[\Lambda], the full and normalized pinned polynomials are related by

\Zpin{G}{\tau}(q;z) =z^{m_G(\tau)}\nZpin{G}{\tau}(q;z); \tag{3}

no division by z is involved. For the empty pinning, \nZpin{G}{\tau}=\Zpart_G. We suppress q when fixed and write \mathcal U_\eps(I)=\{z\in\C:\dist(z,I)<\eps\}.

Lemma 2.1 (Pinned-leaf realization). For every G\in\Gdeg and pinning \tau, there is a graph \widetilde G\in\Gdeg with a pinning \widetilde\tau whose domain consists of leaves, such that

\nZpin{G}{\tau}(z) =\nZpin{\widetilde G}{\widetilde\tau}(z), \qquad \operatorname{girth}(\widetilde G) =\operatorname{girth}(G^\tau).

Proof. Start from G^\tau. For every edge up\in E with u\in V^\tau and p\in\Lambda, attach a distinct leaf \ell_{up} to u and pin it to \tau_p. Each leaf reproduces the corresponding boundary factor in (2), so the normalized polynomials agree. The degree of each free vertex is unchanged from its degree in G, and adding leaves creates no cycle.

Whenever \nZpin{G}{\tau}(x)>0, let \mupin{G}{\tau}{x} be the Gibbs law on \colours^{V^\tau}:

\mupin{G}{\tau}{x}(\varphi) :=\frac{1}{\nZpin{G}{\tau}(x)} \prod_{u\in V^\tau}x^{\bcount_u^\tau(\varphi_u)} \prod_{uv\in E(G^\tau)} \bigl(x\one{\varphi_u=\varphi_v}+\one{\varphi_u\ne\varphi_v}\bigr).

For x>0, this is the usual conditional Gibbs law after pinned-only edge contributions have been removed. At x=0, it is the normalized hard pinned law, which remains meaningful even when \tau is improper.

For r\in V^\tau and a\in\colours, write

\tau^{r=a}:=\tau\cup\{r\mapsto a\}.

Then V^{\tau^{r=a}}=V^\tau\setminus\{r\}, and

\nZpin{G}{\tau}(z) =\sum_{a\in\colours} z^{\bcount_r^\tau(a)}\nZpin{G}{\tau^{r=a}}(z). \tag{4}

The multiplier z^{\bcount_r^\tau(a)} is determined when r is pinned. The normalized function \nZpin{G}{\tau^{r=a}} remains well defined even when this multiplier vanishes at z=0.

2.2Hard-colouring feasibility

A colour c is blocked at a free vertex u when \bcount_u^\tau(c)>0. Its hard effective list is

\hardlist{\tau}{u}:=\set{c\in\colours:\bcount_u^\tau(c)=0}.

A colouring \varphi\colon V^\tau\to\colours is hard-feasible if it is proper on G^\tau and \varphi_u\in\hardlist{\tau}{u} for every u\in V^\tau.

Lemma 2.2 (Hard feasibility). Assume q\ge\Deg+1. For every G\in\Gdeg, every pinning \tau, and every u\in V^\tau,

\abs{\hardlist{\tau}{u}} \ge \deg_{G^\tau}(u)+1.

Consequently \nZpin{G}{\tau}(0)>0.

Proof. At most \abs{N_G(u)\cap\Lambda} colours are blocked at u. Since

\deg_{G^\tau}(u)+\abs{N_G(u)\cap\Lambda} =\deg_G(u)\le\Deg,

we have

\abs{\hardlist{\tau}{u}} \ge q-\abs{N_G(u)\cap\Lambda} \ge \deg_{G^\tau}(u)+1.

A greedy list-colouring of G^\tau, in any vertex ordering, leaves an available colour at every step, so a hard-feasible colouring exists and \nZpin{G}{\tau}(0)>0.

2.3Coupling independence and Wasserstein distance

Let (\mathcal{X},d) be a finite metric space. For probability measures \nu_0,\nu_1 on \mathcal{X},

\Wd(\nu_0,\nu_1) = \inf_{\pi\in\Pi(\nu_0,\nu_1)} \E_{\pi}[d(X,Y)], \tag{5}

where \Pi(\nu_0,\nu_1) denotes the set of couplings of \nu_0 and \nu_1, and X,Y are the two coordinate projections under \pi. On a finite space the infimum is attained. For configurations on a common site set,

\Ham(\sigma,\sigma') :=\abs{\set{u:\sigma_u\ne\sigma'_u}}, \qquad \WHam:=\Wd\ \text{with }d=\Ham.

All Hamming distances below are taken on the common free vertex set.

Definition 2.3 (Potts coupling independence). Let C\in[0,\infty), \mathcal G\subseteq\Gdeg, and J\subseteq[0,1]. We say that \mathcal G satisfies C-coupling independence on J if, for every G\in\mathcal G, every pinning \tau, every r\in V^\tau, all a,b\in\colours, and every x\in J, the two pinned laws are well defined and

\WHam\!\left( \mupin{G}{\tau^{r=a}}{x}, \mupin{G}{\tau^{r=b}}{x} \right)\le C. \tag{6}

They live on the common free set V^\tau\setminus\{r\}. At x=0 they are the normalized hard pinned laws. When \mathcal G=\Gdeg, we simply say that the bounded-degree Potts model satisfies C-coupling independence.

2.4The transfer principle

The following theorem, proved in the main article [SS26], converts the real coupling bounds into complex zero-freeness.

Theorem 2.4 (Potts transfer). Fix integers q,\Deg with \Deg\ge2 and q\ge\Deg+1, and let \mathcal G\subseteq\Gdeg be closed under taking induced subgraphs. Assume:

(i)
\mathcal G satisfies coupling independence at x=0 with constant C_0;
(ii)
for every \delta\in(0,1], it satisfies coupling independence on [\delta,1] with a finite constant C_\delta.

Then there is \eps>0 such that, for every G\in\mathcal G and every pinning \tau,

\nZpin{G}{\tau}(z)\ne0 \qquad\text{whenever }\dist(z,[0,1])<\eps.

Consequently, \Zpin{G}{\tau}(z)=z^{m_G(\tau)}\nZpin{G}{\tau}(z) has only the additional forced zero at z=0 when m_G(\tau)\ge1.

Its positive-temperature induction, also proved in [SS26], is used directly in some sections below.

Lemma 2.5 (Positive-base Potts induction). Fix integers q,\Deg with \Deg\ge2, let \delta\in(0,1] and C\in[0,\infty), and let \mathcal G\subseteq\Gdeg be closed under taking induced subgraphs and satisfy C-coupling independence on [\delta,1]. There are \alpha,\eps>0, depending only on (q,\Deg,\delta,C), such that for every G\in\mathcal G, every pinning \tau, every x\in[\delta,1], and every |z-x|<\eps,

\nZpin{G}{\tau}(z)\ne0,

and, for every v\in V^\tau and a,b\in\colours,

\left|\Log \frac{\nZpin{G}{\tau^{v=a}}(z)/\nZpin{G}{\tau^{v=a}}(x)} {\nZpin{G}{\tau^{v=b}}(z)/\nZpin{G}{\tau^{v=b}}(x)}\right| \le\alpha. \tag{7}

The logarithm is continued from z=x.

3Recalled coupling tools

This section recalls, without proof, the strict Vigoda-threshold results of the main article [SS26] and the soft-flip interface on which several later sections are built.

Theorem 3.1 (Hamming coupling independence on [0,1]). Let q,\Deg be positive integers with \Deg\ge2 and q>11\Deg/6. Put

\gapq:=\frac q\Deg-\frac{11}{6}>0.

Then, for every G\in\Gdeg, every pinning \tau, every x\in[0,1], every r\in V^\tau, and all a,b\in\colours,

\WHam\!\left( \mupin{G}{\tau^{r=a}}{x}, \mupin{G}{\tau^{r=b}}{x} \right) \le \frac{2(1-x)\Deg}{q-(11/6)(1-x)\Deg} \le\frac2{\gapq}.

The two laws are on V^\tau\setminus\{r\}. At x=0 they are well defined by Lemma 2.2; indeed, the hypotheses imply q\ge\Deg+2.

Proposition 3.2 (Vigoda-profile coupling for newly pinned laws). Let q,\Deg be positive integers with \Deg\ge2. For every G\in\Gdeg, every pinning \tau, every r\in V^\tau, all a,b\in\colours, and every x\in(0,1] satisfying q>(11/6)(1-x)\Deg,

\WHam\!\left( \mupin{G}{\tau^{r=a}}{x},\mupin{G}{\tau^{r=b}}{x} \right) \le\frac{2(1-x)\Deg}{q-(11/6)(1-x)\Deg}. \tag{8}

If q>11\Deg/6, the same formula holds at x=0.

Corollary 3.3 (Critical-line coupling input). Let q,\Deg be integers with \Deg\ge2 and q=11\Deg/6. Then \Gdeg satisfies coupling independence at x=0 with a finite constant, and for every \delta\in(0,1] it satisfies coupling independence on [\delta,1] with constant 12/(11\delta).

3.1Soft-flip tools

The soft-flip kernel K_{x,\rho}^{G,\tau} of a profile \rho=(\rho_s)_{s\ge1} samples independent Bernoulli(1-x) coins on the labelled inequality constraints of the pinned system, runs the flip chain with profile \rho on the resulting hard list-colouring instance, and forgets the sampled constraints. The following four lemmas, proved in [SS26], are the interface used below.

Lemma 3.4 (Soft flip kernels). For every profile \rho and x\in(0,1], K_{x,\rho}^{G,\tau} is reversible with stationary law \mupin{G}{\tau}{x}. If \rho_1>0, it is irreducible on \colours^{V^\tau}.

Lemma 3.5 (The two hard instances differ only near v). For adjacent colourings X,Y differing at v, with X_v=a\ne b=Y_v, draw one independent Bernoulli(1-x) coin per labelled constraint and activate that constraint on either side exactly when the coin is one and the inequality is satisfied there. This common-coin construction has the correct activation marginals. The two instances have the same induced graph and lists off v. Their incident edge sets can differ only at neighbours of colour a or b, and their root lists can differ only in those two colours.

Lemma 3.6 (Effect of adding one labelled free–pinned edge). Let two pinned systems have the same free vertex set W, of size m\ge1, and the same labelled constraints except for one additional free–pinned edge in the plus system. For a profile with R_\rho:=\sup_{s\ge1}s\rho_s<\infty, their soft kernels satisfy

\WHam(K_-(\sigma,\cdot),K_+(\sigma,\cdot)) \le\frac{(1-x)R_\rho}{mq} \qquad(\sigma\in\colours^W). \tag{9}

For hard list kernels, deleting one colour from one list gives the bound R_\rho/(mq) on colourings feasible for the smaller list. Adding k labelled free–pinned edges (for hard list kernels, deleting k colours from lists) multiplies the respective bound by k.

Lemma 3.7 (Finite-state continuity of normalized laws). On a finite space \Omega, let two families of nonnegative weights be continuous at x=0, with positive total weights there. Their normalized laws \mu_{0,x},\mu_{1,x} converge in total variation as x\downarrow0, and for every metric d on \Omega,

\Wd(\mu_{0,x},\mu_{1,x})\longrightarrow \Wd(\mu_{0,0},\mu_{1,0}).

Thus a uniform positive-activity coupling bound extends to x=0.

4Zero-free consequences of the transfer principle

This section collects zero-free consequences of the Potts transfer theorem. The first subsection treats the full interval [0,1]; the second treats high-temperature intervals; the third gives the girth-five consequence. For fixed q,\Deg, the full-interval results provide the zero-free input for deterministic approximation of normalized pinned partition functions via Barvinok interpolation and the coefficient-computation framework of [Bar16, PR17]. The coupling inputs are recalled in Section 3.1 and proved in the subsequent sections, except for the independent hard-colouring input on the critical line q=11\Deg/6.

Unless explicitly redefined, this article uses the pinning and normalized-child conventions of Section 2. For probability laws \nu,\nu' on a finite set \Omega, we use

\|\nu-\nu'\|_{\rm TV}:=\frac12\sum_{\omega\in\Omega} |\nu(\omega)-\nu'(\omega)|.

For finite-dimensional vectors, \|\cdot\|_2 is the Euclidean norm; \|\cdot\|_{2\to2} is its induced matrix norm. The local L^2 conventions used for the spectral-gap proof are specified in Section 9.2.

4.1Zero-free neighbourhoods of [0,1]

Theorem 4.1 (Additional Potts zero-free regimes). Let q,\Deg be integers with \Deg\ge2, and assume one of the following:

(i)
q\ge(11/6-1/84000)\Deg;
(ii)
\Deg\ge125 and q\ge1.809\Deg;
(iii)
\Deg\ge3 and q\ge\Deg+3.

There exists \eps=\eps(q,\Deg)>0, and in regime (iii) there also exists g_*=g_*(q,\Deg)\ge3, such that the following holds. For every finite simple graph G of maximum degree at most \Deg and every pinning \tau, with the additional condition \operatorname{girth}(G^\tau)\ge g_* in regime (iii),

\nZpin{G}{\tau}(z)\ne0 \qquad\text{for every }z\in\mathcal U_\eps([0,1]).

Consequently, \Zpin{G}{\tau}(z) has no zeros in the same neighbourhood except possibly at z=0; its order of vanishing there is m_G(\tau).

Remark 4.2 (Literature and algorithmic use of the three [0,1] regimes). Regime (i) continues the strict 11\Deg/6 coupling argument proved in the main article [SS26]. On the critical line, the endpoint input is the hard-colouring coupling of Chen, Feng, Guo, Zhang, and Zou, with the list-contraction estimates originating in the bounded-flip work of Chen, Delcourt, Moitra, Perarnau, and Postle; see [CFG+25, Theorem 20 and Proposition 22] and [CDM+19, Section 6 and Appendix E]. Regime (ii) is the Carlson–Vigoda 1.809\Deg improvement, extended here from the hard endpoint to the full activity interval; compare [CV25]. Regime (iii) uses the large-girth coupling mechanism of [CLMM23], extended here to the soft activity interval.

In contrast, the BBR result below concerns only [x_0,1], not the full activity interval; its conclusion is a high-temperature zero-free neighbourhood.

The following elementary observation isolates the finitely many integer pairs on the critical line that occur in regime (i).

Lemma 4.3 (Integer reduction). Let \Deg and q be integers with 3\le\Deg\le124 and

q\ge\left(\frac{11}{6}-\frac1{84000}\right)\Deg.

Then either q>11\Deg/6, or (\Deg,q)=(6j,11j) for some integer 1\le j\le20.

Proof. The interval [11\Deg/6-\Deg/84000,11\Deg/6] has length less than 1/6. The fractional part of 11\Deg/6 belongs to \{0,1/6,\ldots,5/6\}, so this interval contains an integer only when 11\Deg/6 is itself an integer. Since \gcd(11,6)=1, this means \Deg=6j and q=11j; the bound \Deg\le124 gives j\le20.

Remark 4.4 (The hard endpoint on the critical line). Every integer pair with q=11\Deg/6 and \Deg\ge2 has (\Deg,q)=(6j,11j) for some j\ge1. Thus \Deg\ge6, and the hard-colouring input of [CFG+25, Theorem 20 and Proposition 22] applies along the entire critical line. Its list-contraction input comes from [CDM+19, Section 6 and Appendix E]. To match the pinning conventions, recall that the normalized law at x=0 is the uniform proper list-colouring law on G^\tau, with

\hardlist{\tau}{u}=\{c\in\colours:\bcount_u^\tau(c)=0\}, \qquad |\hardlist{\tau}{u}|-\deg_{G^\tau}(u) \ge q-\Deg=\frac56\Deg.

The conditional weights in [CFG+25, Section 2] likewise omit edges within the pinned set, so this correspondence allows improper \tau. Apply its Theorem 20 to \tau^{r=a} and \tau^{r=b}, and restrict the coupling to V^\tau\setminus\{r\}, to obtain Definition 2.3 at x=0. This supplies the independent endpoint input in Corollary 3.3; the positive-temperature estimate there does not provide a constant uniform as x\downarrow0.

Theorem 4.5 (Coupling inputs in the three additional Potts regimes). Let q,\Deg be integers with \Deg\ge2, and assume one of the three regimes in Theorem 4.1. In regimes (i) and (ii), put \mathcal G=\Gdeg. In regime (iii), let g_*=g_*(q,\Deg) be supplied by Theorem 6.1 and put \mathcal G=\Gdegg{g_*}. There exists C_0=C_0(q,\Deg)<\infty such that \mathcal G satisfies C_0-coupling independence at x=0, and for every \delta\in(0,1] there exists C_\delta=C_\delta(q,\Deg)<\infty such that it satisfies C_\delta-coupling independence on [\delta,1].

In regimes (ii) and (iii), one finite constant may be used for every x\in[0,1]. The same is true in the noncritical cases of regime (i). At the exceptional pairs

(\Deg,q)=(6j,11j),\qquad 1\le j\le20,\quad j\in\mathbb Z,

the endpoint bound is supplied independently by the hard-colouring coupling theorem, while one may take C_\delta=12/(11\delta). No single uniform-in-x constant is asserted at these critical pairs.

Proof. Regime (ii) is Theorem 5.1, and regime (iii) is Theorem 6.1; both theorems give one constant on [0,1].

For regime (i), first suppose \Deg\ge125. Since

\frac{11}{6}-\frac1{84000}-1.809=\frac{681}{28000}>0,

the assertion again follows from Theorem 5.1. If \Deg=2, the integer hypothesis forces q\ge4>11\Deg/6, so Theorem 3.1 applies. Finally, let 3\le\Deg\le124. By Lemma 4.3, either q>11\Deg/6, when Theorem 3.1 applies, or (\Deg,q)=(6j,11j) for 1\le j\le20. In the latter case Corollary 3.3 supplies both the endpoint bound and the stated C_\delta.

Proof of Theorem 4.1. Every listed regime has q\ge\Deg+1. In regimes (i) and (ii), apply Theorem 2.4 to \Gdeg using Theorem 4.5.

In regime (iii), the same two theorems first give a uniform radius for every graph in \Gdegg{g_*}, where g_* is the threshold supplied by Theorem 6.1. For a pair (G,\tau) with \operatorname{girth}(G^\tau)\ge g_*, apply Lemma 2.1. The resulting graph \widetilde G belongs to \Gdegg{g_*} and has the same normalized pinned polynomial, so the established radius applies. The statement for unnormalized pinnings follows from (3).

4.2High-temperature zero-free neighbourhoods

The tree contraction of Bencs, Berrekkal, and Regts [BBR25] gives a further region when the number of colours may be smaller than the maximum degree. Retaining the unrounded contraction parameter gives the following interval.

Theorem 4.6 (A BBR-certified interval at large girth). Let q,\Deg be integers such that

q\ge3, \qquad \frac{\Deg}{q}\ge\frac{e-1/2}{e-1}.

If (q,\Deg)=(3,4), put x_0:=3/4. Otherwise put

k:=e\frac{\Deg-q/2}{\Deg-q}, \qquad x_0:=1-\frac q\Deg \left(1-\frac{k}{\Deg}\right)^2 \frac{\Deg-k}{\Deg-k/2}. \tag{10}

Then 0<x_0<1, and there are g_{\rm BBR}=g_{\rm BBR}(q,\Deg)\ge3 and \eps=\eps(q,\Deg)>0 such that, for every finite simple graph G of maximum degree at most \Deg and every pinning \tau with \operatorname{girth}(G^\tau)\ge g_{\rm BBR},

\nZpin{G}{\tau}(z)\ne0 \qquad\text{for every }z\in\mathcal U_\eps([x_0,1]).

After decreasing \eps, if necessary, so that \eps<x_0, the same zero-free statement holds for the unnormalized pinned polynomial.

Theorem 4.6 addresses the zero-free-neighbourhood question in [BBR25, Section 5]. Outside (q,\Deg)=(3,4), their endpoint is obtained from (10) by replacing k with e^2. Since k\le e^2 and s\mapsto(1-s/\Deg)^3/(1-s/(2\Deg)) is decreasing on (0,\Deg), the interval above contains theirs whenever the latter is nonempty. The exceptional pair has an empty rounded interval and is covered separately here. Indeed, writing t=\Deg-q, the ratio hypothesis gives t/q\ge1/[2(e-1)], and hence

k=e\left(1+\frac{q}{2t}\right)\le e^2.

Proof of Theorem 4.6. For (q,\Deg)=(3,4), the assertion 0<x_0<1 is immediate. Otherwise the ratio hypothesis and integrality imply \Deg\ge q+2: if \Deg=q+1, then the ratio hypothesis forces q=3 and \Deg=4. Writing t=\Deg-q\ge2, we have

\Deg(\Deg-q)-e(\Deg-q/2) =t(t-e)+q(t-e/2)>0,

where for t=2 the right side is positive already at q=3, and for t\ge3 both summands are positive. Hence 0<k<\Deg. Both factors following q/\Deg in (10) lie in (0,1), so again 0<x_0<1.

Let g_{\rm BBR} and C_{\rm BBR} be supplied by Theorem 7.6. Apply Lemma 2.5 to \Gdegg{g_{\rm BBR}}, with \delta=x_0 and C=C_{\rm BBR}. This gives one radius throughout [x_0,1] for every graph in this class and every pinning.

For the free-graph formulation, apply Lemma 2.1 to (G,\tau). The resulting graph lies in \Gdegg{g_{\rm BBR}} and has the same normalized pinned partition function, so the radius just obtained applies. Finally shrink it below x_0/2, so the possible monomial zero of an unnormalized pinning is outside the neighbourhood.

Corollary 4.7 (General-graph high-temperature intervals). Let q,\Deg be integers with \Deg\ge2, and fix x_*\in(0,1]. If

q>\frac{11}{6}(1-x_*)\Deg,

then there is \eps=\eps(q,\Deg,x_*)>0 such that, for every finite simple graph G of maximum degree at most \Deg and every pinning \tau,

\nZpin{G}{\tau}(z)\ne0 \qquad\text{for every }z\in\mathcal U_\eps([x_*,1]).

After decreasing \eps, if necessary, so that \eps<x_*, the same statement holds for the unnormalized pinned polynomial.

Proof. For x\in[x_*,1], Proposition 3.2 gives coupling independence with the following uniform constant, since its bound is decreasing in x:

C_*:= \frac{2(1-x_*)\Deg} {q-(11/6)(1-x_*)\Deg}.

Apply Lemma 2.5 to \Gdeg, with \delta=x_* and C=C_*. This gives the normalized statement. Shrinking the radius below x_* and using (3) gives the unnormalized statement.

4.3Girth-five zero-free neighbourhoods at the (1+\delta)\Deg threshold

Throughout this subsection, \delta\in(0,1] is the slack parameter in q\ge(1+\delta)\Deg. The unrestricted girth-five coupling theorem Theorem 9.4 applies to every residual instance satisfying the degree budget and makes no local short-cycle sparsity assumption.

Theorem 4.8 (Unrestricted girth-five zero-freeness). Fix 0<\delta\le1, let \Deg\ge\Deg_5(\delta) be as in Theorem 9.4, and let q\ge(1+\delta)\Deg. There exists \eps_5=\eps_5(q,\Deg,\delta)>0 such that, for every G\in\Gdeg and every pinning \tau with \operatorname{girth}(G^\tau)\ge5,

\nZpin{G}{\tau}(z)\ne0 \qquad\text{for every }z\in\mathcal U_{\eps_5}([0,1]).

The radius is independent of G and \tau; no bounds on local five-cycle or six-cycle counts are assumed. The unnormalized polynomial \Zpin{G}{\tau}(z) has no zeros in this neighbourhood except possibly at z=0, where its order of vanishing is m_G(\tau). In particular, Z_G(z)\ne0 throughout the same neighbourhood when G itself has girth at least five.

Proof. Since q\ge\Deg+1, Theorems 9.4 and 2.4 give one zero-free radius on the hereditary class \Gdegg{5}. For the stated free-graph condition, apply Lemma 2.1 to (G,\tau): the resulting graph belongs to \Gdegg{5} and has the same normalized pinned polynomial. The same radius therefore applies. The statement for the unnormalized polynomial follows from (3), since the normalized polynomial is nonzero at z=0.

Remark 4.9 (Scope and relation to the spectral-gap input). The spectral local-to-global framework of Chen and Liu [CL26] concerns spectral gaps and rapid mixing on girth-five graphs. Here the all-pinning gap is supplied by Theorem 9.7; the additional coupling-independence argument and zero-free transfer are given in Theorem 9.4 and above. Thus the zero-free statement is a consequence proved here, not a coupling-independence claim attributed to that source.

5Coupling independence for q\ge1.809\,\Deg, \Deg\ge125

Set

m_0:=\frac{1724}{1809}, \qquad \delta_{\rm CV}:=\frac{59}{226125}. \tag{11}

Theorem 5.1 (Hamming coupling independence at 1.809\,\Deg). Let q,\Deg be positive integers with \Deg\ge125 and q\ge1.809\,\Deg. For every G\in\Gdeg, every pinning \tau, every x\in[0,1], every r\in V^\tau, and all a,b\in\colours,

\WHam\!\left( \mupin{G}{\tau^{r=a}}{x}, \mupin{G}{\tau^{r=b}}{x} \right) \le \frac{2}{m_0\delta_{\rm CV}} =\frac{409060125}{50858}<8043.19. \tag{12}

The laws live on V^\tau\setminus\{r\}. At x=0, they are the normalized hard pinned laws.

At x=0, the underlying list-colouring contraction is due to Carlson and Vigoda [CV25, Theorem 4.12 and the proof of Corollary 1.2]. Combined with the stationary-law comparison of [BCC+22, Lemma 4.3], it already yields the corresponding bounded conditional Hamming couplings; the explicit coupling-independence formulation appears in [CFG+25, Theorem 20 and Proposition 21]. This section extends that input to positive activities.

The proof has three stages. Random active constraints first turn the soft Potts law into a mixture of hard list-colouring laws, on which we use the Carlson–Vigoda profile. A coupling matrix for adjacent configurations then combines the Carlson–Vigoda component matches with a product completion, and a geometric path metric gives uniform contraction. Finally, stationary comparison through the root-deleted instance proves Theorem 5.1; the low-multiplicity estimate is certified exactly in Lemma 5.20.

5.1Soft Carlson–Vigoda kernel

The aggregate flip parameters of [CV25, Eq. (1)] are

\begin{aligned} &P_0=0,\quad P_1=1,\quad P_2=\frac{81}{250},\quad P_3=\frac{77}{500},\\ &P_4=\frac{11}{125},\quad P_5=\frac{11}{250},\quad P_6=\frac{11}{1000},\quad P_j=0\quad(j\ge7), \end{aligned} \tag{13}

and we write \boldsymbol P:=(P_j)_{j\ge0}. A feasible alternating component of size j is accepted with probability P_j/j from each of its j proposal vertices, so the aggregate move has transition probability P_j/(nq) on an n-vertex instance. We shall use

\max_j jP_j=1, \qquad \max_j(j-2)P_j=\frac{22}{125}.

Throughout the contraction proof, fix G\in\Gdeg, a pinning \tau, x\in(0,1], and n:=\lvert V^\tau\rvert\ge1; assume \Deg\ge125, q\ge(1809/1000)\Deg, and set \theta:=1-x. We use the free graph G^\tau and boundary counts \bcount_u^\tau(c) from Section 2, which satisfy

\deg_{G^\tau}(u)+\sum_{c\in\colours}\bcount_u^\tau(c) =\deg_G(u)\le\Deg.

The free–pinned constraints retain their individual edge labels, as in Section 3.1, so repeated boundary colours are counted with multiplicity.

Definition 5.2 (Soft-CV kernel). For G\in\Gdeg, a pinning \tau, and x\in(0,1], define

K_{x,\mathrm{CV}}^{G,\tau}:=K_{x,\boldsymbol P}^{G,\tau}.

This is the soft profile kernel of Section 3.1 specialized to (13).

The endpoint x=0 is added in Theorem 5.1 by convergence of the finite-state child laws.

Because component flips are involutions and P_j/j compensates the j proposal vertices, the profile-parametrized argument of Lemma 3.4 shows that K_{x,\mathrm{CV}}^{G,\tau} is irreducible and reversible with stationary law \mupin{G}{\tau}{x}. For adjacent configurations we use the coupled activations of Lemma 3.5; in each marginal the subsequent move is the ordinary hard list-colouring flip transition.

5.2Geometric path metric

Let X,Y\in\colours^{V^\tau} be adjacent with disagreement root v, X_v=a, Y_v=b, T=\set{a,b}. A neighbour u\in N_{G^\tau}(v) is regular if X_u=Y_u\notin T. For regular u define

r_u:=\abs{\set{y\in N_{G^\tau}(u)\setminus\set v:X_y\in T}},\qquad e_u:=\bcount_u^\tau(a)+\bcount_u^\tau(b),\qquad s_u:=\theta\,x^{\,r_u+e_u}. \tag{14}

The survival probability s_u is exactly the probability that, in the active instance, the root edge vu is active, every free T-blocker at u is inactive, and neither target colour is deleted at u. Thus s_u is a deterministic function of the input pair; the probability is over the subsequently sampled active set. Expectations below average both the active-set draw and the flip transition. Write \mathcal U_u for this activation event, so that \Pr(\mathcal U_u)=s_u.

Definition 5.3 (Geometric soft-CV metric). For adjacent X,Y as above set

\ell_x^{G,\tau}(X,Y):=1-\frac{17}{200\,q}\sum_{u\ \text{regular}}s_u , \tag{15}

and let d_x^{G,\tau} be the shortest-path metric generated by these one-coordinate edge lengths on the graph with vertex set \colours^{V^\tau}, in which two configurations are adjacent exactly when they differ at one vertex. The coefficient is (P_2-P_3)/2 per unit of q, matching the hard metric of [CV25, Eq. (2)]. Its limit as x\downarrow0 is the hard metric: a neighbour has limiting survival probability one exactly when it has no blocker and no target deletion, and otherwise has limiting survival probability zero.

Lemma 5.4 (Metric comparison; adjacent geodesics). If q\ge1.809\,\Deg, then m_0\Ham(\sigma,\sigma')\le d_x^{G,\tau}(\sigma,\sigma')\le\Ham(\sigma,\sigma') for all \sigma,\sigma'\in\colours^{V^\tau}, where m_0 is given in (11); for adjacent pairs the direct edge is a geodesic.

Proof. There are at most \Deg regular neighbours and each survival probability is at most 1, so every edge length lies in [1-17\Deg/(200q),1]\subseteq[1724/1809,1]. Any path makes at least \Ham(\sigma,\sigma') coordinate changes, and changing disagreements one at a time costs at most 1 each. A path avoiding the direct adjacent edge uses at least two edges, of cost at least 2m_0>1.

For \sigma,\sigma'\in\colours^{V^\tau} and a disagreement y, put T_y=\set{\sigma_y,\sigma'_y}. Call w an endpoint-common neighbour of y when

w\in N_{G^\tau}(y),\qquad \sigma_w=\sigma'_w\notin T_y.

For such y,w, define the union blocker count

\begin{aligned} b_{\sigma,\sigma'}(y,w) :={}&\abs{\set{s\in N_{G^\tau}(w)\setminus\set y: \sigma_s\in T_y\ \text{or}\ \sigma'_s\in T_y}}\\ &+\sum_{c\in T_y}\bcount_w^\tau(c). \end{aligned}

Thus each free-edge factor is counted once even if it is a blocker in both endpoint configurations, and the edge yw is excluded. Define

\mathcal S_{\rm out}(\sigma,\sigma') :=\sum_{y:\sigma_y\ne\sigma'_y} \theta\!\!\sum_{\substack{w\in N_{G^\tau}(y)\\ \sigma_w=\sigma'_w\notin T_y}} x^{b_{\sigma,\sigma'}(y,w)} . \tag{16}

Lemma 5.5 (A path upper bound for the geometric metric). For all \sigma,\sigma'\in\colours^{V^\tau},

d_x^{G,\tau}(\sigma,\sigma')\le\Ham(\sigma,\sigma') -\frac{17}{200q}\mathcal S_{\rm out}(\sigma,\sigma'). \tag{17}

Proof. Change the disagreements in a fixed order. At the step changing y, every blocker present in the intermediate configuration carries a colour taken from \sigma or from \sigma', so its blocker count at w is at most b_{\sigma,\sigma'}(y,w). Since m\mapsto x^m is nonincreasing for x\in(0,1], each step’s edge length is at most 1-\tfrac{17}{200q}\theta\sum_wx^{b_{\sigma,\sigma'}(y,w)}. Sum along the path.

5.3Conditional coupling under fixed activations

5.3.1Common off-root components

Fix adjacent X,Y\in\colours^{V^\tau} and an outcome of the coupled activations from Lemma 3.5. Write the two active hard instances as

F_X=(V^\tau,E_X,L_X),\qquad F_Y=(V^\tau,E_Y,L_Y).

Here E_X,E_Y are the active free-edge sets, and L_X=(L_{X,u})_{u\in V^\tau}, L_Y=(L_{Y,u})_{u\in V^\tau} are the corresponding effective-list families. The two instances agree away from v. Call every c\notin T a regular colour, and put

\Gamma_c:=\set{u\in N_{G^\tau}(v): X_u=Y_u=c,\ vu\in E_X\cap E_Y},\qquad k_c:=\abs{\Gamma_c}.

Lemma 3.5 implies that an edge vu with common colour c\notin T is active on one side if and only if it is active on the other. For such a regular colour, say that c is root-allowed when

c\in L_{X,v}\cap L_{Y,v}.

The two membership tests are equivalent because the root lists can differ only in the colours a,b. Write

\mathsf A_c:=\one{c\text{ is root-allowed}}.

For a root target c_0\in T, root-allowed means a\in L_{Y,v} when c_0=a, and b\in L_{X,v} when c_0=b. Equivalently it again means c_0\in L_{X,v}\cap L_{Y,v}, since the other starting configuration already uses c_0.

Lemma 5.6 (Components near the disagreement vertex). For each regular colour c\notin T:

1
Deleting v from the root-containing \set{a,c}-component in F_X gives exactly the off-root \set{a,c}-components in F_Y that meet \Gamma_c, with the same post-swap assignments. The analogous statement holds with a,X,Y replaced by b,Y,X. Consequently a root-containing move is feasible exactly when c is root-allowed and all the corresponding off-root moves are feasible.
2
For a fixed off-root proposal vertex and a fixed unordered colour pair, the components grown on the two sides have the same vertex set and the same post-swap feasibility whenever both avoid v. If they differ, at least one contains v, and its flip recolours v.

Proof. By Lemma 3.5, every off-root edge and list is the same in F_X and F_Y. A one-sided root edge has neighbour colour a or b, and a one-sided root deletion deletes a or b. Thus all edges and lists relevant to a colour c\notin T are common away from the root.

Hence the \set{a,c}-component through v on the X-side is v together with exactly the off-root \set{a,c}-components attached through \Gamma_c. These are the same components on the Y-side, because changing the colour at v from a to b does not change the induced \set{a,c} graph away from v. The post-swap assignments agree at every off-root vertex. At v the root-containing swap assigns c; the possible extra deletion of the old colour a is therefore harmless. Thus the only additional root list check is that c is root-allowed, proving part 1. The same off-root identity proves part 2: the component grown from an off-root proposal vertex can first differ only when one growth reaches v, and any nontrivial two-colour flip containing v changes its colour.

Lemma 5.7 (Partition of the aggregate moves). After common off-root aggregate flips are coupled synchronously, every remaining nonidentity aggregate move belongs uniquely to one of the regular-colour families c\notin T or to one of the two root-colour families a,b.

More explicitly, delete v and consider the common off-root \{a,b\}-components. Let \mathcal B_a be those containing an active a-coloured neighbour joined to v on the Y-side, and let \mathcal B_b be those containing an active b-coloured neighbour joined to v on the X-side. Then

\begin{array}{c|c} \text{block class}&\text{assigned moves}\\ \hline \mathcal B_a\setminus\mathcal B_b& \text{$a$-family: $Y$-root and $X$-off-root}\\ \mathcal B_b\setminus\mathcal B_a& \text{$b$-family: $X$-root and $Y$-off-root}\\ \mathcal B_a\cap\mathcal B_b& \text{contained in the two root moves, with no off-root copy}\\ \text{neither}&\text{synchronously coupled}. \end{array}

Proof. When the corresponding components on both sides avoid v, they have the same flipped set, feasibility, and post-swap assignments on that set by Lemma 5.6; these moves are coupled synchronously. Every remaining move either contains v or is an off-root counterpart of a component that contains v. The root-containing component has colour pair \{a,c\} on the X-side or \{b,c\} on the Y-side. If c\notin T, this determines the regular c-family uniquely.

It remains to consider the pair \{a,b\}. Away from v, its components are common to F_X and F_Y. A block reaches v on the Y-side exactly when it belongs to \mathcal B_a, and reaches v on the X-side exactly when it belongs to \mathcal B_b. The four cases in the table follow. In particular, a block meeting both types of root neighbour is part of both root-containing components and is not also counted as an off-root move. This proves both exhaustion and uniqueness.

5.3.2Component matching and coupling completion

Definition 5.8 (Conditional coupling matrix). Let \mathcal M_X and \mathcal M_Y be the side-labelled feasible component moves from X and Y, each augmented by a holding move \varnothing. For M\in\mathcal M_X and N\in\mathcal M_Y, write X^M,Y^N for the outputs and \abs M,\abs N for the numbers of flipped vertices, with X^\varnothing=X, Y^\varnothing=Y, and \abs\varnothing=0. Denote the two move probabilities by \kappa_X(M) and \kappa_Y(N). In particular, a feasible nonholding move of size j has probability P_j/(nq).

A partial coupling matrix is a nonnegative array \boldsymbol\pi=(\pi_{M,N}) satisfying

\sum_N\pi_{M,N}\le\kappa_X(M), \qquad \sum_M\pi_{M,N}\le\kappa_Y(N).

Initialize it at zero. Match every common off-root move with its counterpart, with the full probability on that entry: the flipped sets and their post-swap assignments agree, but the full configurations still differ at v. Leave the holding row and column unassigned. The remaining entries are the aggregate-parameter greedy matches of [CV25, §5.1], specified as follows.

Fix c\notin T. If k_c=0 and c is root-allowed, put the full probability 1/(nq) of the two singleton root moves in their common entry; their outputs agree at v. If c is not root-allowed, neither move is feasible. For k_c\ge1, fix an order of \Gamma_c and assign every distinct off-root component to the first vertex of \Gamma_c that it contains.

If the X-side root-containing \{a,c\}-move is feasible, put its full probability in the entry joining it to a largest opposite off-root \{a,c\}-move. Do the same for the Y-side root-containing \{b,c\}-move. For each family, let its maximum-index set consist of the indices to which a largest component is assigned. If the two sets intersect, choose both entries at one common index; otherwise choose any maximizer in each family. Root feasibility implies feasibility of every constituent off-root move by Lemma 5.6, and the profile is nonincreasing on positive component sizes, so neither entry overfills its opposite row or column.

Subtract these entries, scan \Gamma_c in the fixed order, and at each vertex put the largest possible entry between the two current residual component probabilities assigned there. Each subtraction is made from the component’s global residual, so a component meeting several vertices is never reused. The two flipped sets in such an entry share the indexing vertex and therefore save at least one unit relative to their separate size bounds.

For root colour a, the root-containing move is the Y-side \{a,b\}-move through v, and its possible opposite moves are the X-side off-root \{a,b\}-components meeting an active a-coloured root neighbour but not v; interchange X,Y for root colour b. If there is exactly one such neighbour and both moves are feasible, put the full root-move probability in the root/off-root entry. Otherwise put a feasible root move in the entry with holding on the opposite side. That entry removes the original root disagreement.

Lemma 5.9 (Component matching and product completion). The entries in Definition 5.8 extend to a coupling matrix with row sums \kappa_X and column sums \kappa_Y.

Proof. The regular-colour capacity checks are part of the construction. In particular, a component is recorded at its first, or canonical, vertex of \Gamma_c, and every later match subtracts from its global residual. This covers the case in which one component meets several vertices while the components on the other side are distinct. When the construction uses a root/off-root entry for a root colour with one active neighbour, its eligible partner C satisfies that the root component is \{v\}\cup C. Root feasibility implies feasibility of the off-root move and P_{\abs C+1}\le P_{\abs C}, so the root/off-root entry fits. In every other root-colour case, at most one root move on each side is joined to holding. The proposals whose proposed colour is the current colour give each side holding probability at least 1/q, while a root move has probability at most 1/(nq). Hence the holding entries also fit.

Let the residual row and column probabilities be

\alpha_M:=\kappa_X(M)-\sum_N\pi_{M,N}, \qquad \beta_N:=\kappa_Y(N)-\sum_M\pi_{M,N}. \tag{18}

They are nonnegative by the preceding checks. Both move distributions have total mass one, and each specified entry removes the same mass from a row and a column, so

\sum_M\alpha_M =1-\sum_{M,N}\pi_{M,N} =\sum_N\beta_N =:R.

If R>0, add

\frac{\alpha_M\beta_N}{R}

to every entry (M,N); if R=0, nothing remains. This product completion has residual row sums \alpha_M and column sums \beta_N, and therefore gives the required coupling matrix.

Lemma 5.10 (Cost of the completed coupling). For the residual masses in (18), the product-completion entries have total Hamming increment at most

\sum_M\alpha_M\abs M+\sum_N\beta_N\abs N.

An entry matching a common off-root move has zero increment. An explicit root-colour move paired with holding saves two units relative to the flipped-set-size bound. Every nonidentity move occurs in exactly one component family.

Proof. For every pair of moves,

\Ham(X^M,Y^N)-1\le\abs M+\abs N,

because away from the two flipped sets only the original disagreement can remain. Consequently the product-completion cost is at most

\sum_M\alpha_M\abs M+\sum_N\beta_N\abs N.

This proves the displayed residual bound. A common off-root match leaves only the original disagreement and hence has zero increment. An explicit root-colour move paired with holding changes the root to its colour on the opposite side. For such an X-side move M, \Ham(X^M,Y)-1\le |M|-2, and symmetrically on the other side. This is the stated two-unit saving relative to the size bound. Finally, Lemma 5.7 ensures that every nonidentity move occurs in exactly one family. Thus, even when a product-completion entry joins moves from different families, its two size terms are charged separately to the unique families of its row move and column move; no residual mass is omitted or counted twice.

For the rest of this section, let (X_1,Y_1) denote the outputs drawn from the completed coupling matrix.

For every c\notin T, define its physical root multiplicity by

m_c:=\abs{\set{u\in N_{G^\tau}(v):X_u=Y_u=c}},

and recall that k_c=\abs{\Gamma_c} is its active root multiplicity. For the current active outcome, put

\mathcal C_{\rm low}:= \set{c\notin T:c\text{ is root-allowed},\ m_c\in\set{1,2}},

and let E_v be the event that at least one selected component move recolours v.

Lemma 5.11 (Conditional component budgets). Fix a coupled active outcome for adjacent X,Y, with disagreement root v, X_v=a, Y_v=b, and put T=\set{a,b}. The following facts hold for the component coupling above.

1
Root-event budget. Conditionally on the active outcome,
nq\,\Pr(E_v\mid F_X,F_Y) \le q-P_2\sum_{c\in\mathcal C_{\rm low}}k_c . \tag{19}
2
Output-discount bound. Fix a regular neighbour u and w\in N_{G^\tau}(u)\setminus\set v which is not initially T-coloured. For each t\in T, collect the active free edges from w to a t-coloured vertex and the active pinned-neighbour constraints at w deleting t. After root-recolouring moves have been charged to E_v, the total transition probability that can recolour w into a colour of T is at most (1+P_2)/(nq) whenever at least one collected constraint is active. If none is active and the root edge vu is active while all off-root T-blockers and target deletions at u are inactive, the same-neighbour matrix entry is at least (1-P_2)/(nq) and flips only u on either side. Credits obtained this way for different ordered pairs (u,w) refer to different summands of (17).

Proof. For part 1, assign the X-side \{a,c\} and Y-side \{b,c\} root-containing flips to the regular colour c\notin T; the two remaining \{a,b\} root flips form the a- and b-families. These assignments are disjoint. A colour that is not root-allowed contributes no root-changing move, except possibly a or b; for those exceptional colours the extra proposal is the current colour on its witness side and hence is a stay proposal, while it is forbidden on the other side. Thus it contributes zero. For c\notin T with k_c=0, the two root-containing components are both the singleton \set v and are coupled together with probability 1/(nq). If k_c\ge1, each root-containing component has size at least k_c+1, so their combined probability is at most 2P_{k_c+1}/(nq). When k_c=1,

2P_2\le1-P_2 \qquad\text{because}\qquad 3P_2=\frac{243}{250}\le1,

and when k_c=2,

2P_3\le1-2P_2 \qquad\text{because}\qquad 2P_3+2P_2=\frac{239}{250}\le1 .

Hence every c\in\mathcal C_{\rm low} saves at least P_2k_c from its unit baseline. All other regular colours cost at most their unit baseline. Assign the X-side root-containing \set{a,b}-move to the b-baseline and the Y-side root-containing move to the a-baseline. Each has probability at most P_1/(nq)=1/(nq), so summing the q baselines and multiplying by nq proves (19).

For part 2, fix a target t\in T and compare the two \set{X_w,t}-components from w. If both avoid v, by Lemma 5.6 they are identical and hence synchronously coupled, so they contribute only one copy of their component probability. If a component contains v, its move is already charged to E_v; after removing all such moves, again at most one off-root component remains. Its probability is at most \max_jP_j/(nq)=1/(nq). If an active free edge joins w to an off-root t-coloured vertex, that component has size at least two and its probability is at most P_2/(nq); if an active pinned-neighbour constraint deletes t at w, the component is infeasible. In either case one target contributes at most P_2/(nq) and the other at most 1/(nq). The remaining possibility is that the active constraint is the edge wv. Then w is itself a regular root neighbour. After the two root-containing moves are assigned to E_v, the possible off-root moves are the two opposite-target components through w. If both are singletons, let r_1,r_2 be their remaining probabilities multiplied by nq, after the root/off-root entries have been assigned, taking zero for an infeasible move. Since each original move has probability at most 1/(nq), we have 0\le r_1,r_2\le1. The same-neighbour rule couples residual mass \min\{r_1,r_2\}/(nq). Hence, outside E_v, the probability that at least one of these moves occurs is at most

\frac{r_1+r_2-\min\{r_1,r_2\}}{nq} =\frac{\max\{r_1,r_2\}}{nq}\le\frac1{nq}.

If either is not a singleton, its probability is at most P_2/(nq), while the other is at most 1/(nq). Thus this case also has total probability at most (1+P_2)/(nq), proving the assertion for every active collected constraint.

Under the safe event in the last assertion, the two target components at u are feasible singletons. Each has probability P_1/(nq)=1/(nq). A root-containing component meeting the active edge vu has size at least two and consumes at most P_2/(nq) of the corresponding singleton in the root/off-root entry. The same-neighbour entry therefore has probability at least (1-P_2)/(nq) on both sides. It flips only u, to opposite colours in T, and leaves every other vertex unchanged. Thus its output correction in (17) is indexed by the ordered pair (u,w). Different ordered pairs are different terms of the double sum there (even if they share one endpoint), so summing these credits cannot reuse one metric summand. The same coupled move may realize several such savings simultaneously, in which case its path-metric correction is exactly the sum of the corresponding (u,w)-summands.

5.4Geometric discount estimates

Recolouring a unique blocker to a fresh colour creates discount; recolouring the root, the regular neighbour, or an off-root neighbour can destroy it. The following three lemmas bound these effects.

Put

\alpha_{\mathrm{fr}}:=q-\Deg-2 . \tag{20}

For a regular neighbour u, let \mathsf{SB}_u be the activation event that vu is active, exactly one of the r_u other free T-blocker edges at u is active, and every remaining T-blocker edge and T-coloured pinned-neighbour constraint at u is inactive. Write

b_u^{\rm SB}:=\Pr(\mathsf{SB}_u),

where the probability is over the active-constraint draw.

Lemma 5.12 (Fresh-colour gain). Fix a regular neighbour u with R=r_u free target blockers and e=e_u target pinned-neighbour constraints. The expected increase of the output u-discount relative to its deterministic input value s_u, caused by singleton recolourings of its blockers, is at least

\frac{\alpha_{\mathrm{fr}}}{nq}\, b_u^{\rm SB},

and

b_u^{\rm SB}= \begin{cases} R\,\theta^2x^{R+e-1},&R\ge1,\\ 0,&R=0. \end{cases}

Proof. The displayed probability is over the active-set draw: the root edge is active, exactly one blocker edge is active, and all other blockers and all e target-deleting pinned-neighbour constraints are inactive — independent activation bits of distinct constraints. Equivalently, the factor R\theta^2x^{R+e-1} is the sum, over the R possible unique blocker incidences, of the deterministic discount increment available on the corresponding activation event; it is not an additional probability factor for the singleton flip below. Fix a blocker incidence (u,s). At s, exclude the two target colours, every colour of its full free neighbourhood, and every colour forbidden by one of its pinned-neighbour constraints: at least

q-2-\left(\deg_{G^\tau}(s)+\sum_{c\in\colours}\bcount_s^\tau(c)\right) \ge\alpha_{\mathrm{fr}}

colours remain, and for each the alternating component of s is a list-feasible singleton in every active outcome, accepted with probability P_1=1 and transition mass 1/(nq). The flip removes one blocker incidence and raises the corresponding output u-discount relative to s_u by \theta x^{R+e-1}-\theta x^{R+e}=\theta^2x^{R+e-1}. Summing over the \alpha_{\mathrm{fr}} colours and R incidences gives the claim; if one blocker vertex serves several regular neighbours, the single flip increases the total discount by the sum of the individual increments. Incidence summation therefore counts each discount contribution, while the flip probability is counted once.

For a regular root-neighbour colour c, recall that m_c is its physical multiplicity, and recall that \bcount_v^\tau(c) counts the root pinned-neighbour constraints forbidding c. Define

L_x:=\sum_{\substack{c\notin T:\\m_c\in\set{1,2}}} m_c\,x^{\bcount_v^\tau(c)},\qquad \phi_x:=\frac{L_x}{\Deg} . \tag{21}

Since L_x is a weighted subcount of the physical root neighbours, 0\le \phi_x\le1. The factor x^{\bcount_v^\tau(c)} is the probability that c survives in the active root list, and root-edge activation is independent of root boundary activation, so the expected value of \sum_{c\in\mathcal C_{\rm low}}k_c is exactly \theta L_x. Averaging (19) from Lemma 5.11 therefore gives

nq\,\Pr(E_v)\;\le\;q-P_2\,\theta L_x , \tag{22}

where E_v is the root-recolouring event. This is the soft analogue of [CV25, Eq. (18)], proved directly for the two active hard instances.

Lemma 5.13 (Ordered-incidence discount bound). Fix a regular neighbour u and w\in N_{G^\tau}(u)\setminus\set v not initially a target blocker, so X_w=Y_w\notin T. Let \mathcal O_w be the following disjoint set of physical constraint factors:

\mathcal O_w:= \set{wy\in E(G^\tau):y\ne u,\ X_y\in T\ \text{or}\ Y_y\in T} \ \sqcup\ \set{(w,t,j):t\in T,\ 1\le j\le\bcount_w^\tau(t)} ,

and put t_w=\abs{\mathcal O_w}. The contribution of the ordered incidence (u,w) to input discount loss minus certified output discount is at most (1+P_2)\,s_u/(nq).

Proof. Let \mathcal E_w be the event that all of \mathcal O_w is inactive. Given the active outcome, for each target c\in T the operations recolouring w into c flip the unique active \set{X_w,c}-component of w in one marginal, with transition probability at most \max_jP_j/(nq)=1/(nq), so their total probability is at most 2/(nq) always. When \mathcal E_w fails, some constraint of \mathcal O_w is active at w: an active edge to a c-coloured vertex forces the \set{X_w,c}-component to have size at least two, capping its transition probability at P_2/(nq), and an active pinned-neighbour constraint forbidding c makes the swap list-infeasible. Part 2 of Lemma 5.11 shows directly that root-containing moves are already charged to E_v and common off-root components are coupled synchronously, so the remaining probability is at most (1+P_2)/(nq). This proves in the two-instance setting the case-(i) estimate corresponding to [CV25, §4.3]. The averaged probability is thus at most \bigl((1+P_2)+(1-P_2)x^{t_w}\bigr)/(nq), and each new blocker incidence costs at most s_u-s_ux=\theta s_u of discount.

The activation bits of \mathcal U_u are disjoint from those of \mathcal E_w, so \Pr(\mathcal U_u\cap\mathcal E_w)=s_u x^{t_w}. On this event both target components at u — the \set{X_u,a}-move on one side and the \set{X_u,b}-move on the other — are feasible singletons; root-containing components meeting the active root edge have transition probability at most P_2/(nq), so after the root/off-root entry each side retains probability at least (1-P_2)/(nq), and the same-neighbour entry pairs the two moves: the coupled flip recolours u to a on one side and to b on the other, creating a new disagreement at u with pair \set{a,b}. Its blocker incidences at w are exactly the t_w constraints of \mathcal O_w (no other vertex changes), so the (u,w) output discount in (17) is \theta x^{t_w}. The certified credit is at least (1-P_2)\,s_u\theta x^{2t_w}/(nq). The net cost is at most

\frac{s_u\,\theta}{nq}\Bigl[(1+P_2) +(1-P_2)\bigl(x^{t_w}-x^{2t_w}\bigr)\Bigr] \le\frac{(1+P_2)\,s_u}{nq},

since for t_w\ge1, x^{t_w}-x^{2t_w}\le x and (1-x)[(1+P_2)+(1-P_2)x]\le1+P_2, with slack x[2P_2+(1-P_2)x]\ge0; for t_w=0 the extra term vanishes. Distinct ordered incidences certify distinct summands of (17), so no credit is reused.

Lemma 5.14 (Expected loss of the geometric discount). Fix the adjacent input pair and a deterministic order of the off-root neighbours of each regular u. For each coupled outcome, process in order the root recolouring, a recolouring of u into T, and then the off-root neighbours in the fixed order. Let \mathsf{Loss}_u be the telescoping decrease of the input u-discount caused by these operations, charging each decrease at its first cause. Let \mathsf{Credit}_u be the sum of the distinct (u,w)-indexed output-score summands certified by the same-neighbour matches in Lemmas 5.11 and 5.13. Thus every input loss is charged once and every output summand is credited at most once. Expectations are over both the coupled activation draw and the coupled hard update. For every regular neighbour u,

\begin{gathered}\E[\mathsf{Loss}_u]-\E[\mathsf{Credit}_u] \;\le\;\frac{\beta^{+}_x}{nq}\,s_u ,\\ \beta^{+}_x:=q-P_2\theta L_x+(1+P_2)\Deg+2 .\end{gathered}

Proof. The discount at u can disappear in three ways: the root is recoloured — probability bounded by (22); the root survives but u is recoloured into a target colour — by Lemma 5.6, common off-root components are coupled synchronously, whereas every non-common component meeting the root is already charged to E_v; after those moves are removed, each target contributes probability at most 1/(nq), hence at most 2/(nq) in total; or a neighbour w creates a new blocker — at most \Deg ordered incidences, each bounded by Lemma 5.13. The three types can overlap on a single operation, but each charge separately upper-bounds the part of the discount loss it names and the total loss telescopes over the triggered types, so summing the three expected charges is conservative.

Lemma 5.15 (Disjointness of the output credits). For every coupled outcome, the sum of all output-score summands retained as credits in Lemmas 5.12, 5.13, and 5.14 is at most \mathcal S_{\rm out}(X_1,Y_1).

Proof. The ordered-incidence credit associated with (u,w) is the summand of (16) indexed by the output disagreement at u and its endpoint-common neighbour w. The deterministic ordering in Lemma 5.14 retains each such ordered pair at most once. The fresh-colour credit at a regular root neighbour u is instead the summand indexed by the surviving root disagreement (v,u). These summands have first coordinate v, whereas every ordered-incidence summand has first coordinate u\ne v; the two collections are therefore disjoint. If a single coupled flip realizes several credits, they are distinct summands in the defining double sum for \mathcal S_{\rm out}. Their total is consequently bounded by the full output score, outcome by outcome.

5.5Per-colour charge estimates

Set \varrho=q/\Deg, \eta(\varrho)=\frac{P_2-P_3}{2\varrho}=\frac{17}{200\varrho}, and

\gamma_{\rm gain}:=\eta(\varrho) \Bigl(\varrho-1-\frac2\Deg\Bigr),\qquad \gamma_{\rm loss}:=\eta(\varrho) \Bigl(\varrho-P_2\theta\phi_x+1+P_2+\frac2\Deg\Bigr), \tag{23}

the per-\Deg metric corrections supplied by Lemmas 5.12 and 5.14. On \varrho\ge1809/1000, \Deg\ge125, these coefficients lie in the half-open range

(\gamma_{\rm gain},\gamma_{\rm loss})\in \left[\frac{13481}{361800},\frac{17}{200}\right) \times\left[0,\frac{799}{5400}\right], \qquad \frac{799}{5400}<P_2.

Indeed,

\gamma_{\rm gain}=\frac{17}{200} \left(1-\frac{1+2/\Deg}{\varrho}\right),\qquad \gamma_{\rm loss}=\frac{17}{200} \left(1+\frac{1+P_2+2/\Deg-P_2\theta\phi_x}{\varrho}\right).

Over the displayed continuous parameter domain, the first expression has its minimum at (\varrho,\Deg)=(1809/1000,125) and approaches 17/200 without reaching it; the second has its maximum at (\varrho,\Deg,\theta\phi_x)=(1809/1000,125,0). For the finite maximization, close the open endpoint and use the closed bounding rectangle

\mathcal R_\gamma:= \left[\frac{13481}{361800},\frac{17}{200}\right] \times\left[0,\frac{799}{5400}\right]. \tag{24}

For any coefficient pair in this rectangle, set

\begin{aligned} \Lambda_1&:=2-P_2+\gamma_{\rm loss},& \Lambda_2&:=2-P_3-\gamma_{\rm gain},\\ \Lambda_3&:=2-P_2+2P_3-2P_4,& \Lambda_{\rm low}&:=\max\set{\Lambda_1,\Lambda_2,\Lambda_3}. \end{aligned} \tag{25}

5.5.1Finite component encoding

Definition 5.16 (Finite component records). Fix a regular colour c with k_c\ge1, order \Gamma_c=\set{u_1,\ldots,u_{k_c}}. At u_i, record the size of the Y-side off-root \set{a,c}-component and the size of the X-side off-root \set{b,c}-component. A component meeting several u_i is recorded at its first listed incidence; its later appearances receive the marker 0, which represents no move and has P_0=0.

Replace every positive recorded size at least 7 by 7, and denote the resulting record sizes by a_i,b_i. These are truncated sizes, not necessarily the physical sizes. The truncation changes no transition mass: such an off-root component has mass zero, and a root-containing component containing it has size at least 8 and also has mass zero. Put

R_X=1+\sum_i a_i,\qquad R_Y=1+\sum_i b_i.

Let \chi_i,\upsilon_i be the available flags of the a- and b-records, respectively. Let

\xi_i:=\one{\text{the $Y$-side $\{a,c\}$-flip recorded by $a_i$ is feasible}},\qquad \zeta_i:=\one{\text{the $X$-side $\{b,c\}$-flip recorded by $b_i$ is feasible}} .

For a positive record, the availability flags are explicitly

\chi_i=\one{a\in L_{X,u_i}}=\one{a\in L_{Y,u_i}}, \qquad \upsilon_i=\one{b\in L_{X,u_i}}=\one{b\in L_{Y,u_i}},

where the equalities use the common off-root lists. If a_i=0, set \chi_i=\xi_i=0; if b_i=0, set \upsilon_i=\zeta_i=0. Moreover,

\xi_i\le\chi_i,\qquad \zeta_i\le\upsilon_i,\qquad a_i=1\Longrightarrow\xi_i=\chi_i,\qquad b_i=1\Longrightarrow\zeta_i=\upsilon_i.

Indeed, a feasible swap must place its target colour legally at the recording neighbour, while for a singleton this is its only post-swap list check. Thus every realized record satisfies these restrictions.

Let w_X=\mathsf A_c\prod_{i:a_i>0}\xi_i and w_Y=\mathsf A_c\prod_{i:b_i>0}\zeta_i be the root-component feasibility weights. Following Definition 5.8, choose

i_X\in\arg\max_{i:a_i>0}a_i, \qquad i_Y\in\arg\max_{i:b_i>0}b_i,

using the same index whenever a common maximizer exists. Among the permitted pairs, choose one that maximizes the right-hand side of (26) below. All move masses in this record are multiplied by nq; thus a feasible size-j move has scaled mass P_j. Define the record upper charge for this arbitrary multiplicity:

\mathcal H_c= w_X(R_X-a_{i_X}-1)P_{R_X} +w_Y(R_Y-b_{i_Y}-1)P_{R_Y} +\sum_i\bigl(a_i\alpha_i+b_i\beta_i-\min\set{\alpha_i,\beta_i}\bigr), \tag{26}

where

\alpha_i=\xi_iP_{a_i}-w_X\one{i=i_X}P_{R_X},\qquad \beta_i=\zeta_iP_{b_i}-w_Y\one{i=i_Y}P_{R_Y}

are the remaining scaled off-root masses. The first two terms are the root/off-root matches; after their masses are subtracted, the sum is the residual match through the same u_i. Thus (26) is the conservative record used to bound the coupling above. It is defined for every k_c\ge1 and both values of \mathsf A_c. The cases \mathsf A_c=1, k_c\in\set{1,2} are handled by Lemma 5.20. Finally, define

N_{11}(c):=\abs{\set{i:a_i=b_i=1,\ \chi_i=\upsilon_i=1}}, \qquad N_{12}(c):=\abs{\set{i:\set{a_i,b_i}=\set{1,2},\ \chi_i=\upsilon_i=1}} .

The first index set uses the ordered pair (1,1), whereas the second uses (1,2) or (2,1). They are therefore disjoint, and hence

N_{11}(c)+N_{12}(c)\le k_c. \tag{27}

A repeated appearance is never counted by N_{11}(c). Omitting a possible N_{12}(c) credit at such an appearance is conservative because that term enters with a minus sign.

For a regular colour c with k_c=0, set

\mathcal H_c:=-\mathsf A_c, \qquad N_{11}(c):=N_{12}(c):=0.

Lemma 5.17 (Graph-to-record domination). For every regular colour c, its contribution to the conditional expected Hamming increment, after multiplication by nq, is at most \mathcal H_c. When k_c=0, this means that the contribution is at most -\mathsf A_c, which is the convention used below.

Proof. Suppose first that k_c\ge1. A root-containing component consists of the root and its disjoint off-root components. Matching it to the opposite component indexed by i_X, or by i_Y, therefore leaves at most R_X-a_{i_X}-1, or R_Y-b_{i_Y}-1, new disagreements per unit of matched mass. These give the first two terms of (26).

After those masses are subtracted, the two residual moves recorded at u_i have masses \alpha_i,\beta_i and flipped-set sizes a_i,b_i. Their maximal match has mass \min\{\alpha_i,\beta_i\}. Both flipped sets contain u_i, so its Hamming increment is at most

a_i\alpha_i+b_i\beta_i-\min\{\alpha_i,\beta_i\}.

If the components share additional vertices, the actual increment is smaller; this is why \mathcal H_c is an upper charge rather than an exact cost. Every remaining one-sided probability is passed to the product completion and bounded by its flipped-set size. Summing over the canonical indices gives (26); a repeated appearance has the zero marker and contributes no second copy.

If k_c=0 and c is root-allowed, the two singleton root moves are coupled and remove the sole input disagreement, giving increment -1. If c is unavailable, there is no move in this family and its contribution is 0. These are exactly the two values of -\mathsf A_c.

The geometric coefficients range over the rectangle (24), but the finite verification need not inspect a subdivision of that rectangle. The following elementary observation reduces it to one coefficient pair.

Lemma 5.18 (Balancing-point domination). For real numbers g_{\rm gain},g_{\rm loss}, put

\mathcal L(g_{\rm gain},g_{\rm loss}):= \max\set{2-P_2+g_{\rm loss},\ 2-P_3-g_{\rm gain},\ \Lambda_3}

and, for a fixed component record of a regular colour c, define its excess by

\mathcal E_c(g_{\rm gain},g_{\rm loss}):= \mathcal H_c+g_{\rm loss}N_{11}(c)-g_{\rm gain}N_{12}(c) +1-k_c\mathcal L(g_{\rm gain},g_{\rm loss}).

Then

\mathcal E_c(g_{\rm gain},g_{\rm loss}) \le \mathcal E_c\!\left(\frac{19}{500},\frac{33}{250}\right).

At this balancing pair, all three terms in the maximum defining \mathcal L equal 226/125; the pair belongs to \mathcal R_\gamma in (24).

Proof. Set

u_{\rm loss}:=g_{\rm loss}-\frac{33}{250},\qquad u_{\rm gain}:=\frac{19}{500}-g_{\rm gain},\qquad M:=\max\set{0,u_{\rm loss},u_{\rm gain}}.

The identities

2-P_2+\frac{33}{250} =2-P_3-\frac{19}{500} =\Lambda_3=\frac{226}{125}

give

\mathcal L(g_{\rm gain},g_{\rm loss})=\frac{226}{125}+M.

Consequently,

\begin{aligned}\mathcal E_c(g_{\rm gain},g_{\rm loss}) -\mathcal E_c\!\left(\frac{19}{500},\frac{33}{250}\right) &=u_{\rm loss}N_{11}(c)+u_{\rm gain}N_{12}(c)-k_cM\\ &\le M\bigl(N_{11}(c)+N_{12}(c)-k_c\bigr)\le0,\end{aligned}

where the last inequality is (27).

Two observations connect the finite expression to the geometric estimates.

Loss charge. The geometric charge \gamma_{\rm loss} is levied only at the N_{11}(c) locations. This covers the discount budget of Lemma 5.14: a location with a record of size at least two carries an active T-blocker, hence lies outside \mathcal U_u, the safe event defining s_u, and no discount is at risk there; and across the availability split, \theta\bigl[x^{\bcount_v^\tau(c)}x^{r_u+e_u}+(1-x^{\bcount_v^\tau(c)})\bigr]\ge \theta x^{r_u+e_u}=s_u. The unavailable contribution appears separately as (1-\mathsf A_c)k_c below.

Gain credit. The N_{12}(c) credit \gamma_{\rm gain} is claimed only at locations with exactly one active blocker edge and both targets surviving — an event contained in the fresh-gain event of Lemma 5.12; distinct colours claim disjoint incidences, so the credited mass never exceeds the gain supplied.

For c_0\in T=\{a,b\}, let C_{c_0}(F_X,F_Y) denote nq times the charged Hamming increment, including the coalescence saving, to the \{a,b\}-component family assigned to target c_0 by Definition 5.8 and Lemma 5.10. Put

\mathcal H_T(F_X,F_Y):=C_a(F_X,F_Y)+C_b(F_X,F_Y).

Lemma 5.19 (Drift decomposition by colour). For coupled active instances F_X,F_Y and each c\notin T, retain \mathsf A_c=\one{c\text{ is root-allowed}}. Let \mathcal H_c(F_X,F_Y) be the record upper charge (26) when k_c\ge1, with root-containing masses set to zero when \mathsf A_c=0; for k_c=0 put \mathcal H_c=-\mathsf A_c. With \mathcal H_T(F_X,F_Y) as defined above, put

\mathcal D:=\E[d_x^{G,\tau}(X_1,Y_1)]-d_x^{G,\tau}(X,Y).

All expectations in this statement are over the coupled activation draw and the coupled hard transition from the fixed adjacent input pair. Then the one-step metric drift satisfies

\begin{aligned} nq\,\mathcal D\le \E\Bigg[\,\mathcal H_T(F_X,F_Y) +\sum_{c\notin T} \Bigl\{\mathcal H_c+ \gamma_{\rm loss}\bigl(\mathsf A_c N_{11}(c)+ (1-\mathsf A_c)k_c\bigr) -\gamma_{\rm gain}\mathsf A_c N_{12}(c)\Bigr\}\,\Bigg]. \end{aligned} \tag{28}

Here N_{11}(c)=N_{12}(c)=0 when k_c=0.

Proof. Put \omega=17/(200q). Lemmas 5.7, 5.9, and 5.10 partition, complete, and bound the cost of all aggregate moves, while Lemma 5.17 bounds the actual regular-colour Hamming contribution by its record upper charge. Write

S_{\rm in}:=\sum_{u\ {\rm regular}}s_u, \qquad S_{\rm out}:=\mathcal S_{\rm out}(X_1,Y_1).

Thus Lemma 5.5 first gives

nq\,\mathcal D \le \E\!\left[\mathcal H_T(F_X,F_Y)+ \sum_{c\notin T}\mathcal H_c\right] +nq\,\omega\bigl(S_{\rm in}-\E[S_{\rm out}]\bigr). \tag{29}

Fix the output-discount allocation as follows. The root, target-recolouring, and ordered-incidence terms used in Lemma 5.14 are allocated first; they do not use the fresh increments of Lemma 5.12. Allocate those fresh increments next, and discard any remaining output discount. This is legitimate outcome by outcome by Lemma 5.15. With b_u^{\rm SB}=\Pr(\mathsf{SB}_u) as defined above, the two lemmas then give

S_{\rm in}-\E[S_{\rm out}] \le \frac{\beta_x^+}{nq}\sum_{u\ {\rm regular}}s_u -\frac{\alpha_{\mathrm{fr}}}{nq}\sum_{u\ {\rm regular}}b_u^{\rm SB} .

By (23),

\omega\beta_x^+=\gamma_{\rm loss},\qquad \omega\alpha_{\mathrm{fr}}=\gamma_{\rm gain}.

It remains to turn these two averaged discount bounds into the pointwise colour terms in (28). For a physical regular neighbour u of colour c, let \iota_u indicate that vu is active, and let N^j_{c,u} be one exactly when u is the first recorded incidence of its component and is counted by N_{1j}(c), and zero otherwise, for j=1,2. Thus N^1_{c,u} contributes to N_{11}(c) and N^2_{c,u} contributes to N_{12}(c). Root-list survival is independent of all root-edge and blocker bits, and

\E\!\left[\mathsf A_c N^1_{c,u} +(1-\mathsf A_c)\iota_u\right] =x^{\bcount_v^\tau(c)}s_u+ \bigl(1-x^{\bcount_v^\tau(c)}\bigr)\theta \ge s_u .

Moreover, \mathsf A_c N^2_{c,u}=1 entails exactly one active target blocker at u and survival of both targets, so \E[\mathsf A_c N^2_{c,u}]\le b_u^{\rm SB}. Summing over neighbours, using k_c=\sum_{u:X_u=Y_u=c}\iota_u, and applying the two coefficient identities proves (28).

There is no duplicated charge or credit: Lemma 5.7 partitions the hard moves; \mathsf A_c and 1-\mathsf A_c are disjoint; N_{11}(c) and N_{12}(c) are disjoint; and each N_{12}(c) credit is attached to its own blocker incidence. If one flip improves several such incidences, Lemma 5.12 counts the corresponding sum of distinct metric-discount increments.

5.5.2Small multiplicities: exact finite verification

Lemma 5.20 (Finite low-multiplicity estimate). For every regular colour c with \mathsf A_c=1 and k_c\in\set{1,2}, every component state encoded above and every (\gamma_{\rm gain},\gamma_{\rm loss}) in the rectangle (24) satisfy

\mathcal H_c+\gamma_{\rm loss}N_{11}(c) -\gamma_{\rm gain}N_{12}(c) \le-1+k_c\Lambda_{\rm low}. \tag{30}

The maximum excess of the left-hand side over the right-hand side of (30), over the stated records and coefficient pairs, is 0, attained at the balancing pair.

Computer-assisted proof. By Lemma 5.18, it is enough to check the single coefficient pair

(\gamma_{\rm gain},\gamma_{\rm loss}) =\left(\frac{19}{500},\frac{33}{250}\right), \qquad \Lambda_{\rm low}=\frac{226}{125}.

Exact rational enumeration gives maximum excess zero over all 400 structural states and 400 permitted maximizer choices for k_c=1, and all 193600 structural states and 196964 permitted maximizer choices for k_c=2. These include every admissible availability and feasibility pattern, repeated-component marker, truncated size, and choice among tied maximum components. For example, equality at the balancing pair is attained by the one-index record a_1=2, b_1=1 with all four availability and feasibility flags equal to 1: then \mathcal H_c=423/500, N_{11}(c)=0, and N_{12}(c)=1.

Every component configuration maps to one of these records: order its listed neighbour incidences as in Definition 5.16, write 0 after the first listed incidence of a repeated component, truncate every size at 7, and retain its actual availability and feasibility flags. The permitted records use one state at size 0, two at size 1, and three at each size 2,\ldots,7, exactly as justified in that definition. The enumeration also allows some records that no graph realizes; this only enlarges the maximum and is therefore conservative.

The companion Lean development proves this finite estimate and the encoding of the actual component configurations in ZeroFreeness/Coupling/CV/Certificate.lean and its dependent modules; the finite arithmetic is checked by Lean’s kernel without importing Python output [Shi26]. As an independent check, the Python verifier anc/python/soft_cv_certificate_verifier.py checks the larger eleven-pair test specified in anc/CERTIFICATE_SPEC.md. This includes the balancing pair above, every permitted maximum-component tie, and an equality witness. The Python source and frozen certificate are covered by anc/SHA256SUMS. For reproducibility, the exhaustive checks are run from the repository root with

python3 anc/python/soft_cv_certificate_verifier.py --check

and the reported state counts are part of the certificate specification.

Lemma 5.21 (High multiplicity and missing colours). Set

\Lambda_{\rm bulk}:=\tfrac43+P_2+\tfrac43P_4=\tfrac{1331}{750}.

For a root-allowed regular colour c with k_c\ge3 active neighbours,

\mathcal H_c+\gamma_{\rm loss}N_{11}(c) \le-1+\Lambda_{\rm bulk}k_c.

For a regular colour c absent from the active root list,

\mathcal H_c+\gamma_{\rm loss}k_c \le \frac{39743}{27000}k_c\le\Lambda_{\rm bulk}k_c.

The second inequality is strict when k_c>0.

Proof. The root-containing components have size at least k_c+1\ge4, so in (26) each root/off-root term is at most \max_{r\ge4}(r-2)P_r=2P_4, giving 4P_4 for the two sides. For the contribution at one regular neighbour, \max_{1\le r,s\le7} \bigl(rP_r+sP_s-\min\set{P_r,P_s}\bigr)=1+P_2. Indeed, \max_j jP_j=1 and \max_j(j-1)P_j=P_2; subtracting the smaller of P_r,P_s leaves one term of each type. Equality occurs at (r,s)=(2,1). A location receives the geometric charge \gamma_{\rm loss}\le P_2 only when both records are singletons, in which case its component term is at most 1. Either way the location contributes at most 1+P_2. Hence the total is at most 4P_4+k_c(1+P_2), and

4P_4+k_c(1+P_2)\le-1+\Lambda_{\rm bulk}k_c,

with slack (k_c-3)(1+4P_4)/3\ge0; the same bound in the aggregate-parameter hard setting is [CV25, Lemma 4.6]. If the colour is missing from the active root list there are no root-containing moves, and the exact per-neighbour maximum is 1+P_2 by the same calculation, matching [CV25, Lemma 4.7]; adding the largest geometric correction \gamma_{\rm loss}\le799/5400 gives 39743/27000<\Lambda_{\rm bulk}.

Lemma 5.22 (The two root colours). Fix c_0\in\set{a,b}. For the two root colours, define

\begin{aligned} k_a&:=\bigl|\{u\in N_{G^\tau}(v):X_u=Y_u=a,\ vu\in E_Y\}\bigr|,\\ k_b&:=\bigl|\{u\in N_{G^\tau}(v):X_u=Y_u=b,\ vu\in E_X\}\bigr|. \end{aligned}

Thus each multiplicity is counted on the side where the corresponding root-containing move starts. The cost C_{c_0}(F_X,F_Y) defined above for the corresponding \set{a,b}-component moves satisfies

C_{c_0}(F_X,F_Y)\le-\one{c_0\text{ is root-allowed}} +\Lambda_{\rm bulk}k_{c_0}.

Proof. If c_0 is unavailable there is no root-containing move and the off-root components meet disjoint sets of the k_{c_0} neighbours. After the common denominator nq is cleared, each contributes at most one, so C_{c_0}(F_X,F_Y)\le k_{c_0}\le\Lambda_{\rm bulk}k_{c_0}. Let c_0 be available. If k_{c_0}=0, the singleton root move paired with holding probability contributes -1. If k_{c_0}\ge2, an infeasible root move leaves cost at most k_{c_0}\le\Lambda_{\rm bulk}k_{c_0}-1; a feasible one paired with holding probability has total cost at most

k_{c_0}+\max_j(j-2)P_j=k_{c_0}+\tfrac{22}{125},

including the off-root component moves, and 2\Lambda_{\rm bulk}-1-(2+\tfrac{22}{125}) =\tfrac{28}{75}>0 settles the weakest case k_{c_0}=2. If k_{c_0}=1, let the unique component left after deleting v from the root-containing component have size s. By the block classification in Lemma 5.7, on the opposite side it either avoids v and is the unique off-root partner in this family, or it also reaches v and belongs to the other root-colour move, leaving no off-root copy here. In the first case, because the target colour is root-allowed, the root-containing flip is feasible exactly when its sole off-root component is feasible. Thus an infeasible root move contributes 0. A feasible root move with no feasible off-root partner is paired with holding probability at cost \max_s(s-1)P_{s+1}=\tfrac{22}{125}; and a feasible pair costs sP_s-(s+1)P_{s+1}\le\tfrac{44}{125}. All are below \Lambda_{\rm bulk}-1, with slack at least \tfrac{317}{750}.

5.6Averaging and degree bounds

5.6.1Averaging over active multiplicities

A physical regular root colour c of multiplicity m_c\ge3 has random active multiplicity K_c\sim\mathrm{Bin}(m_c,\theta). Thus K_c denotes the random multiplicity before the activations are exposed, whereas k_c=\abs{\Gamma_c} denotes its value for a fixed active outcome. In the root-allowed case, the corrected per-colour contribution for 1\le K_c\le2 is bounded by (30), whose positive coefficient is at most

\overline\Lambda_{\rm low}:= 2-P_2+\tfrac{799}{5400}=\tfrac{49247}{27000};

for K_c\ge3 use \Lambda_{\rm bulk} from Lemma 5.21 and discard the negative credit. In the root-missing case the rate is 39743/27000<\Lambda_{\rm bulk} for every K_c. After the allowed case’s -1 baseline is separated, the expected positive charge per physical neighbour is therefore at most

\Lambda_{\rm bulk}\theta+ (\overline\Lambda_{\rm low}-\Lambda_{\rm bulk}) \theta x^{m_c-2}\bigl(1+(m_c-2)\theta\bigr) \le\Lambda_{\rm bulk},

since \theta x^{m_c-3}(1+(m_c-2)\theta)\le2 and 3\Lambda_{\rm bulk}-2\overline\Lambda_{\rm low} =22627/13500>0. Thus both availability cases cost at most \Lambda_{\rm bulk} per physical neighbour after the baseline is separated. The baseline is accounted for in Lemma 5.23.

5.6.2Degree budget

Let

L:=\sum_{\substack{c\notin T\\m_c\in\set{1,2}}}m_c,\qquad H:=\deg_{G^\tau}(v)-L,\qquad B_v^{\partial}:=\sum_{c\in\colours}\bcount_v^\tau(c).

Then L+H+B_v^{\partial}\le\Deg and, because L_x\le L,

(L-L_x)+H+B_v^{\partial}\le\Deg-L_x. \tag{31}

Every distinct colour missing from the active root list is witnessed by an active pinned-neighbour constraint forbidding that colour. Choosing one witness for each missing colour is injective, so their number is at most the number of active root pinned-neighbour constraints, and hence at most B_v^{\partial}.

Lemma 5.23 (The drift envelope). Let \mathcal D be the expected one-step drift of d_x^{G,\tau} under the coupling above. Then

nq\,\mathcal D\;\le\;-q +\theta\Lambda_{\rm low}L_x +\Lambda_{\rm bulk}(\Deg-L_x). \tag{32}

Proof. Apply the drift decomposition (28). Its regular-colour summand is exactly the expression controlled by Lemmas 5.20 and 5.21; the root-colour summand has no geometric correction because the input metric discounts only regular neighbours.

Condition on the root pinned-neighbour constraint coins; they determine the active root list and are independent of all root-edge and blocker bits. Every colour c contributes a baseline: an available colour contributes -1 — through Lemma 5.10 when it has no active neighbour, through (30) when 1\le k_c\le2, through Lemma 5.21 when k_c\ge3, and through Lemma 5.22 for the two target colours — while a missing colour contributes 0. The witness injection above charges each missing baseline to a distinct root pinned-neighbour constraint.

For each allowed low-multiplicity colour c, root availability is independent of the root-edge bits, so \E[k_c\one{\text{allowed}}]=\theta m_cx^{\bcount_v^\tau(c)}, and each active neighbour carries at most \Lambda_{\rm low} by (30). Their total is at most \theta\Lambda_{\rm low}L_x. Neighbours of unavailable low colours have expected count

\theta\sum_{\substack{c\notin T\\m_c\in\set{1,2}}} m_c(1-x^{\bcount_v^\tau(c)})\le L-L_x

and rate at most 39743/27000<\Lambda_{\rm bulk} each. Physical high-multiplicity regular neighbours are charged at most \Lambda_{\rm bulk} each by the binomial averaging above, in both availability cases; root-colour neighbours at most \Lambda_{\rm bulk} each by Lemma 5.22. Finally, missing baselines cost at most one per pinned-neighbour constraint, and 1<\Lambda_{\rm bulk}. Hence

nq\,\mathcal D\le-q+\theta\Lambda_{\rm low}L_x +\Lambda_{\rm bulk}\bigl[(L-L_x)+H+B_v^{\partial}\bigr],

and (31) proves (32).

5.7Numerical bound and contraction

Lemma 5.24 (Final numerical inequality). For \varrho\ge1809/1000, \Deg\ge125, and \theta,\phi\in[0,1], interpret \phi_x=\phi in (23). Then

-\varrho+\Lambda_{\rm bulk}(1-\phi) +\theta\phi\,\max\set{\Lambda_1,\Lambda_2,\Lambda_3} \;\le\;-\frac{59}{226125},

where the rates in (25) are evaluated at the actual coefficients (23); in particular \Lambda_3=226/125.

Proof. Write \eta_0=17/200, y=\theta\phi, and C_\Deg=1+P_2+2/\Deg. For j=1,2,3, set

F_j:=-\varrho+\Lambda_{\rm bulk}(1-\phi)+y\Lambda_j.

For the first case this expression is

F_1=-\varrho+\Lambda_{\rm bulk}(1-\phi) +y(2-P_2+\eta_0) +\frac{\eta_0}{\varrho}y(C_\Deg-P_2y).

For fixed y we have y\le\phi, so \phi=y maximizes F_1. The resulting function decreases in \varrho and as \Deg grows. At (\varrho,\Deg)=(1809/1000,125) its derivative in y is decreasing in y and at y=1 equals \tfrac{34097}{1809000}>0. Thus the first case is maximized at that corner and y=\phi=\theta=1.

For the second case,

\Lambda_2=2-P_3-\eta_0+ \frac{\eta_0}{\varrho}\left(1+\frac2\Deg\right)>0.

First maximize in \theta, and then in the affine variable \phi, to obtain

F_2\le-\varrho+\max\set{\Lambda_{\rm bulk},\Lambda_2}.

Both -\varrho+\Lambda_{\rm bulk} and -\varrho+\Lambda_2 decrease in \varrho, and the latter also decreases as \Deg grows. Hence their maximum occurs at (\varrho,\Deg)=(1809/1000,125); there \Lambda_2-\Lambda_{\rm bulk}=\tfrac{61637}{1809000}>0, so \phi=\theta=1 is the maximizer at the worst corner. Finally \Lambda_3=226/125>\Lambda_{\rm bulk}, and the same affine maximization gives F_3\le-\varrho+\Lambda_3.

Exact evaluation gives the three gaps

\frac{59}{226125},\qquad\frac{59}{226125},\qquad\frac1{1000},

whose minimum is \delta_{\rm CV}. The scalar_closure certificate in anc/python/soft_cv_certificate_verifier.py verifies all three corner values.

Theorem 5.25 (Geometric soft-CV contraction). Let q,\Deg be positive integers with \Deg\ge125 and q\ge1.809\,\Deg. For every G\in\Gdeg and pinning \tau with n=\lvert V^\tau\rvert\ge1, every x\in(0,1], and every adjacent pair X,Y\in\colours^{V^\tau}, there is a coupling (X_1,Y_1) of K_{x,\mathrm{CV}}^{G,\tau}(X) and K_{x,\mathrm{CV}}^{G,\tau}(Y) such that

nq\Bigl(\E[d_x^{G,\tau}(X_1,Y_1)]-d_x^{G,\tau}(X,Y)\Bigr) \le-\delta_{\rm CV}\Deg. \tag{33}

Proof. Use the common-coin coupling of Lemma 3.5 and the conditional component coupling of Definition 5.8 and Lemma 5.9. The drift envelope (32), which combines the component charges and geometric-discount estimates, applies to this coupling. Lemma 5.24 bounds its right-hand side by -\delta_{\rm CV}\Deg. At x=1 the metric is Hamming and the active graph is empty. The endpoint x=0 is handled below by continuity of the normalized child laws, not by assigning values to 0^0 in the active representation.

5.8From contraction to coupling independence

It remains to compare each child kernel with the common middle kernel and apply stationary comparison in the child metric.

Lemma 5.26 (Soft-CV child–middle row discrepancy). Let G\in\Gdeg, let \tau be a pinning, let r\in V^\tau, let c\in\colours, and fix x\in(0,1]. Define the middle kernel by

K_{{\rm mid},x}:=K_{x,\mathrm{CV}}^{G-r,\tau}.

Its free graph is G^\tau-r, with the original boundary counts restricted to V^\tau\setminus\{r\}. Thus r and all its incident interactions are deleted without adding the pinned-neighbour constraints created by pinning r=c. If the common vertex set V^\tau\setminus\{r\} has n_0\ge1 vertices, then for every configuration \sigma\in\colours^{V^\tau\setminus\{r\}},

\WHam\bigl(K_{x,\mathrm{CV}}^{G,\tau^{r=c}}(\sigma), K_{{\rm mid},x}(\sigma)\bigr) \le\frac{(1-x)\Deg}{n_0q} \le\frac{\Deg}{n_0q}.

If q\ge1.809\,\Deg, the same bound holds in the child metric d_x^{G,\tau^{r=c}}\le\Ham.

Proof. The child differs from the middle instance by at most \Deg pinned-neighbour constraints. Apply the common one-boundary estimate Lemma 3.6 with \rho_j=P_j. The CV parameters satisfy \sup_j jP_j=1, so the Hamming bound is (1-x)\Deg/(n_0q)\le\Deg/(n_0q). Under the additional parameter assumption, Lemma 5.4 gives d_x^{G,\tau^{r=c}}\le\Ham, so the same coupling gives the metric bound.

Proof of Theorem 5.1. Fix G\in\Gdeg, a pinning \tau, a root r\in V^\tau, and colours a,b. If a=b, the laws coincide. Let n_0=\abs{V^\tau\setminus\{r\}}. If n_0=0, both children are the empty point mass, so assume n_0\ge1 and first take x>0.

Let K_{\rm mid}:=K_{x,\mathrm{CV}}^{G-r,\tau}, whose stationary law is \mu_{\rm mid}:=\mupin{G-r}{\tau}{x}. For c\in\{a,b\}, put

\mu_c:=\mupin{G}{\tau^{r=c}}{x}.

Fix such a c, and write d_c:=d_x^{G,\tau^{r=c}} for the child metric. Then Theorem 5.25 and Lemma 5.4 gives, for adjacent X,Y,

\begin{aligned} W_{1,d_c}\!\left( K_{x,\mathrm{CV}}^{G,\tau^{r=c}}(X), K_{x,\mathrm{CV}}^{G,\tau^{r=c}}(Y)\right) &\le d_c(X,Y)-\frac{\delta_{\rm CV}\Deg}{n_0q}\\ &\le\left(1-\frac{\delta_{\rm CV}\Deg}{n_0q}\right) d_c(X,Y). \end{aligned}

By Lemma 5.26, the child–middle row discrepancy is at most (1-x)\Deg/(n_0q) in this metric. Stationary comparison with contraction gap \delta_{\rm CV}\Deg/(n_0q) therefore yields

W_{1,d_c}(\mu_c,\mu_{\rm mid}) \le\frac{1-x}{\delta_{\rm CV}}.

Since d_c\ge m_0\Ham,

\WHam(\mu_c,\mu_{\rm mid}) \le\frac{1-x}{m_0\delta_{\rm CV}}.

Applying this for c=a,b and using the triangle inequality through \mu_{\rm mid} gives

\WHam(\mu_a,\mu_b) \le\frac{2(1-x)}{m_0\delta_{\rm CV}} \le\frac{2}{m_0\delta_{\rm CV}}.

At x=0, hard feasibility (Lemma 2.2, q\ge\Deg+1) makes both hard child partition sums positive, and Lemma 3.7 passes the uniform bound to their normalized hard limits. This proves (12) also at x=0.

6Coupling independence for q\ge\Deg+3 at large girth

Theorem 6.1 (Large-girth coupling independence). Let q,\Deg be integers with \Deg\ge3 and q\ge\Deg+3. There exist g_*=g_*(q,\Deg)\ge3 and C_*=C_*(q,\Deg)<\infty such that, for every G\in\Gdeg and every pinning \tau with \operatorname{girth}(G^\tau)\ge g_*, the bound below holds for every x\in[0,1], every r\in V^\tau, and all a,b\in\colours:

\WHam\!\left( \mupin{G}{\tau^{r=a}}{x}, \mupin{G}{\tau^{r=b}}{x} \right)\le C_*.

The two laws live on the common free set V^\tau\setminus\{r\}. At x=0 they are well defined by Lemma 2.2.

At x=0, the estimate is already contained in [CLMM23, Theorem 5.10 and Lemma 5.13]; it is also recovered below by continuity. To obtain the interval [0,1], we extend the same tree argument to positive activities. For 0<x<1, the soft recursion is a weighted-colour recursion whose scaled cavity messages are subdistributions. Four units of palette slack below the root give a uniform contraction. The contraction implies tree total-influence decay (TID) and relative strong spatial mixing (SSM) after a fixed depth; the root factors are handled by two exact cancellations. The large-girth transfer of [CLMM23] then applies, and finite-state continuity supplies the value at x=0.

6.1Weighted tree recursion

We first take 0<x<1 and put s:=1-x. Root the free component of a tree of maximum degree at most \Deg and condition on a fixed pinning, treating every pinned neighbour as a boundary constraint. At a free vertex v, let d_v be the number of free children and k_v the number of pinned neighbours. As in Section 2, \bcount_v^\tau(c) counts those of colour c. Thus

d_v+k_v\le\Deg-1

away from the root, while d_v+k_v\le\Deg at the root. Define

a_v(c)=x^{\bcount_v^\tau(c)},\qquad A_v=\sum_{c=1}^q a_v(c),\qquad \underline A_v=q-sk_v. \tag{34}

Bernoulli’s inequality gives

A_v\ge\underline A_v. \tag{35}

If p_i is the cavity marginal of free child i, put m_i=sp_i. The parent recursion is

p_v(c)= \frac{a_v(c)\prod_{i=1}^{d_v}(1-m_i(c))} {\sum_{b=1}^q a_v(b)\prod_{i=1}^{d_v}(1-m_i(b))}, \qquad m_v=sp_v. \tag{36}

Every m_i is a subdistribution, meaning a nonnegative vector of total mass at most one; here its total mass is exactly s. More importantly, for every non-root vertex,

\underline A_v-d_v =q-sk_v-d_v \ge q-k_v-d_v\ge4. \tag{37}

At the root the same calculation leaves three units of slack. As in the hard proof of [CLMM23], contraction is required only below the root; the first step is retained as a bounded, possibly noncontracting map.

To integrate the Jacobian between two finite messages, we need a convex domain that contains every genuine non-root message and every interpolation point used in potential coordinates. Put

\mathcal D_s :=\left\{m\in[0,1/4]^q: \sum_{c\in\colours}m(c)\le s\right\}. \tag{38}

This is a convex down-set. The pointwise bound below shows that every genuine non-root scaled message belongs to \mathcal D_s and has total mass exactly s; the extra points in (38) occur only along a potential-coordinate interpolation.

We use the elementary product inequality

0<B<1,\quad 0\le y_j\le B,\quad \sum_jy_j\le1 \quad\Longrightarrow\quad \prod_j(1-y_j)\ge(1-B)^{1/B}. \tag{39}

Indeed, concavity of \log(1-y) on the chord from 0 to B gives \log(1-y)\ge y\log(1-B)/B. Since the coefficient is negative,

\sum_j\log(1-y_j) \ge\frac{\log(1-B)}B\sum_jy_j \ge\frac{\log(1-B)}B,

which proves the claim after exponentiation.

At a non-root vertex, inputs m_i\in\mathcal D_s already give the crude invariant bound

\begin{aligned} Z_v &:=\sum_b a_v(b)\prod_i(1-m_i(b))\\ &\ge A_v-\sum_i\sum_b a_v(b)m_i(b) \ge A_v-d_v\ge\underline A_v-d_v\ge4. \end{aligned} \tag{40}

Consequently p_v(c)\le1/4 and m_v=sp_v belongs to \mathcal D_s. This proves invariance by induction from the leaves; the sharper estimate below will also provide the coordinate bounds used in the weighted norm.

6.2Uniform contraction below the root

We choose

\phi(t)=2\operatorname{arctanh}\sqrt t, \qquad \phi'(t)=\frac1{\sqrt t(1-t)} \tag{41}

because its derivative factorizes the transformed Jacobian into one factor depending on the outgoing marginal and one measuring the incoming occupancy of a single colour. In the original probability coordinate the same potential is \psi_s(p)=\phi(sp). The map \phi is increasing and concave on [0,1/4]; write

\boldsymbol\phi(m):=(\phi(m(c)))_{c\in\colours}.

For the local map (m_1,\ldots,m_{d_v})\mapsto p_v, define

J^p_{v,i} :=D\boldsymbol\phi(p_v)\, \frac{\partial p_v}{\partial m_i}\, \bigl(D\boldsymbol\phi(m_i)\bigr)^{-1}, \qquad J^p_v:=(J^p_{v,1}\mid\cdots\mid J^p_{v,d_v}).

The superscript p indicates that this auxiliary Jacobian has the unscaled output p_v and the scaled inputs m_i. Let \widehat J_{v,i} and \widehat J_v=(\widehat J_{v,1}\mid\cdots\mid\widehat J_{v,d_v}) denote the analogous blocks with the scaled output \boldsymbol\phi(m_v). At a zero coordinate these matrices mean their continuous extensions from positive coordinates.

For a block Jacobian J=(J_1,\ldots,J_d), a positive parent weight w, and positive child weights w_i, put

\norm{J}_{\mathbf w} =\sup_{(h_i)\ne0} \frac{w\norm{\sum_iJ_ih_i}_2} {\max_i w_i\norm{h_i}_2}. \tag{42}

For d=0 this empty block norm is zero. Below, \norm{J^p_v}_{2\to2} denotes the spectral norm of the horizontally concatenated q-by-d_vq block Jacobian.

Lemma 6.2 (Exact Jacobian factorization). Write \Sigma_v(c)=\sum_i m_i(c) and

F_{1,v}=\max_{c\in\colours}\bigl(1-p_v(c)\bigr)^{-2}, \qquad F_{2,v}=\max_{c\in\colours}p_v(c)\Sigma_v(c).

Then \norm{J^p_v}_{2\to2}^2\le F_{1,v}F_{2,v}.

Proof. Write p=p_v and \gamma(c)=\sqrt{p(c)}/(1-p(c)). Differentiating the \phi-transformed recursion gives

(J^p_{v,i})_{c,b} =\gamma(c)\bigl(p(b)-\one{b=c}\bigr)\sqrt{m_i(b)}.

Hence, for a unit vector h,

\norm{J^p_v}_{2\to2}^2 =\max_{\norm{h}_2=1}\sum_c\Sigma_v(c) \bigl(\gamma(c)h(c)-p(c)\langle\gamma,h\rangle\bigr)^2 .

Set u(c)=\gamma(c)h(c) and U_1=\sum_cu(c)=\langle\gamma,h\rangle. The constraint \norm h_2=1 becomes

\sum_c\frac{u(c)^2(1-p(c))^2}{p(c)}=1.

Since p(c)\Sigma_v(c)\le F_{2,v}, the identity

\sum_c\frac{(u(c)-p(c)U_1)^2}{p(c)} =\sum_c\frac{u(c)^2}{p(c)}-U_1^2

gives

\begin{aligned} \sum_c\Sigma_v(c)(u(c)-p(c)U_1)^2 &\le F_{2,v}\sum_c\frac{(u(c)-p(c)U_1)^2}{p(c)}\\ &\le F_{2,v}\sum_c\frac{u(c)^2}{p(c)} \le F_{1,v}F_{2,v}. \end{aligned}

We next bound the two factors. The quantity B_v controls each coordinate of p_v, while \zeta_v records the loss in the occupancy estimate.

Lemma 6.3 (Pointwise marginal bound). Consider (36) at a non-root vertex v with m_i\in\mathcal D_s for every free child. With d=d_v and \underline A=\underline A_v, define

\xi_v=\left(\frac43\right)^{4d/(\underline A-1)}, \qquad B_v=\frac{\xi_v}{\underline A-1+\xi_v}. \tag{43}

Then

\frac{p_v(c)}{1-p_v(c)} \le\frac{\xi_v}{\underline A-1}, \qquad p_v(c)\le B_v\le\frac14, \qquad m_v(c)\le\frac14 \tag{44}

for every colour c. In particular, m_v\in\mathcal D_s.

Proof. The crude estimate (40) already gives p_v(c)\le1/4. For the sharper recursive estimate, the claim is immediate if a_v(c)=0. Otherwise set S=A_v-a_v(c)\ge\underline A-1. Weighted AM–GM and a_v(b)\le1 give

\begin{aligned}\sum_{b\ne c}a_v(b)\prod_i(1-m_i(b)) &\ge S\prod_{b\ne c} \left(\prod_i(1-m_i(b))\right)^{a_v(b)/S}\\ &\ge S\prod_i \left(\prod_{b\ne c}(1-m_i(b))\right)^{1/S}.\end{aligned}

By (39) with B=1/4, the inner product is at least (3/4)^4. The function S\mapsto S(3/4)^{4d/S} is increasing, so

\frac{p_v(c)}{1-p_v(c)} \le \frac1{S(3/4)^{4d/S}} \le \frac{\xi_v}{\underline A-1}.

Finally \underline A\ge d+4 implies \xi_v/(\underline A-1)\le1/3. For d=0 this is immediate; for d\ge1 it reduces to (4/3)^{4d/(d+3)}\le(d+3)/3, whose logarithmic derivative is nonnegative after equality at d=1. This proves B_v\le1/4 and hence all of (44). The induction starts at a free leaf, where the same argument has d=0.

For every non-root vertex y, define its local \xi_y,B_y by (43), with v replaced by y, and put

\zeta_y= \left(\frac{\underline A_y-1}{\xi_y}+1\right) \log\left(1+\frac{\xi_y}{\underline A_y-1}\right)-1. \tag{45}

For a child y_i indexed by i, abbreviate the corresponding quantities by B_i:=B_{y_i} and \zeta_i:=\zeta_{y_i}.

Lemma 6.4 (Occupancy-factor bound). Under the hypotheses of Lemma 6.3, suppose in addition that each free-child input satisfies m_i(c)\le B_i for all c. Then, for every colour c,

p_v(c)\sum_{i=1}^{d_v}m_i(c) \le \frac1{e\underline A_v} \exp\left\{ \frac1{\underline A_v}\sum_{i=1}^{d_v}(\zeta_i+1) \right\}. \tag{46}

Proof. For fixed c, the (d_v+1)-term AM–GM inequality gives

a_v(c)\prod_i(1-m_i(c))\sum_i m_i(c)\le e^{-1}.

The definition gives B_i>0, while the same slack calculation as in Lemma 6.3 gives B_i\le1/4. Writing Z_v=\sum_b a_v(b)\prod_i(1-m_i(b)) for the recursion denominator, weighted AM–GM, a_v(b)\le1, and (39) give

\begin{aligned}Z_v &\ge A_v\prod_b \left(\prod_i(1-m_i(b))\right)^{a_v(b)/A_v}\\ &\ge A_v\prod_i \left(\prod_b(1-m_i(b))\right)^{1/A_v}\\ &\ge A_v\prod_i(1-B_i)^{1/(A_vB_i)}\\ &\ge \underline A_v \prod_i(1-B_i)^{1/(\underline A_vB_i)}.\end{aligned}

The last step uses that t\mapsto t\exp(-H/t) is increasing for fixed H\ge0. Since B_i^{-1}\log(1/(1-B_i))=\zeta_i+1, division proves (46).

Lemma 6.5 (Weighted Jacobian contraction). At each non-root vertex set w_v=(1-\zeta_v)^{-1/2}, and for a child y_i write w_i:=w_{y_i}. For every 0<x<1, every fixed pinning, and every collection of free-child inputs m_i\in\mathcal D_s satisfying m_i(c)\le B_i, the transformed recursion in (36) satisfies

\norm{\widehat J_v}_{\mathbf w}\le \rho:=\exp\left(-\frac4{81q}\right)<1. \tag{47}

Moreover

1\le w_v\le e^{1/12}, \tag{48}

Proof. First reduce to the unscaled output. Regard p_v in (36) as a recursion with weighted colour availability a_v(c) and subdistribution inputs m_i. The calculation below is first made in the relative interior of \prod_i\mathcal D_s; the displayed formulas extend continuously to the whole closed domain, including when an input coordinate tends to zero. The chain rule with (41) gives

\widehat J_{v,i} =\operatorname{diag}\left( \frac{\sqrt s(1-p_v(c))}{1-sp_v(c)} \right)_{c=1}^q J^p_{v,i}. \tag{49}

The diagonal factor is at most one because

1-st-\sqrt s(1-t) =(1-\sqrt s)(1+\sqrt s\,t)\ge0 \qquad(0\le t\le1).

Thus it is enough to bound the unscaled Jacobian with Lemma 6.2. That factorization uses only \sum_cp_v(c)=1 and \Sigma_v(c)\ge0, not \sum_bm_i(b)=1; the weighted colour availability enters only through Z_v, controlled by Lemmas 6.3 and 6.4. Bounding F_{1,v}\le \exp\bigl(2\xi_v/(\underline A_v-1)\bigr) by Lemma 6.3 and F_{2,v} by (46), and using d_v\le\underline A_v-4 to produce the term -4/\underline A_v, yields

\norm{J^p_v}_{2\to2}^2 \le\frac1{\underline A_v} \exp\left\{ \frac{2\xi_v}{\underline A_v-1}-\frac4{\underline A_v} +\frac1{\underline A_v}\sum_i\zeta_i \right\}. \tag{50}

Let y_v=\xi_v/(\underline A_v-1)\le1/3. The elementary entropy inequality [CLMM23, Fact B.5] used in the weighted colouring recursion gives

0<\zeta_v<1,\qquad \frac1{1-\zeta_v}\le e^{y_v/2}, \tag{51}

and therefore (48). Directly from (42),

\norm{J}_{\mathbf w}^2 \le \norm{J}_{2\to2}^2 w_v^2\sum_iw_i^{-2}.

Here w_i^{-2}=1-\zeta_i, so \sum_iw_i^{-2}=d_v-\sum_i\zeta_i. Applying this bound to (50) gives

\begin{align}\norm{\widehat J_v}_{\mathbf w}^2 &\le \exp\left\{ \frac{5\xi_v}{2(\underline A_v-1)}-\frac8{\underline A_v} \right\}. \tag{52}\end{align}

Indeed, with \bar\zeta_v=\underline A_v^{-1}\sum_i\zeta_i,

\left(\frac{d_v}{\underline A_v}-\bar\zeta_v\right)e^{\bar\zeta_v} \le\frac{d_v}{\underline A_v} \le1-\frac4{\underline A_v} \le e^{-4/\underline A_v}.

It remains to retain a strict margin. Since d_v\le\underline A_v-4,

\xi_v\le\frac{256}{81} \exp\left(-\frac{12\log(4/3)}{\underline A_v-1}\right).

Writing u=(\underline A_v-1)^{-1} and using \log(1+u)\le u\le12\log(4/3)u shows

\xi_v\frac{\underline A_v}{\underline A_v-1}\le\frac{256}{81}.

Consequently the exponent in (52) is at most -8/(81\underline A_v)\le-8/(81q). Taking square roots proves (47). If d_v=0, the Jacobian is zero and the conclusion is immediate.

Lemma 6.6 (From Jacobian contraction to message contraction). Fix the local colour weights at a non-root vertex v and the child structural parameters that determine B_i,w_i. Let (m_i)_{i=1}^{d_v} and (m'_i)_{i=1}^{d_v} be two collections in \mathcal D_s such that m_i(c),m'_i(c)\le B_i for every i,c, and let m_v,m'_v be their respective outputs under (36). Then

w_v\norm{\boldsymbol\phi(m_v)-\boldsymbol\phi(m'_v)}_2 \le \rho\max_i w_i\norm{\boldsymbol\phi(m_i)-\boldsymbol\phi(m'_i)}_2 . \tag{53}

Both sides are interpreted as zero when d_v=0.

Proof. When d_v=0, the two outputs are identical. Otherwise, for t\in[0,1] define the potential-coordinate segment

u_i(t)=(1-t)\boldsymbol\phi(m_i)+t\boldsymbol\phi(m'_i), \qquad m_i(t)=\boldsymbol\phi^{-1}(u_i(t)).

Write u(t)=(u_i(t))_{i=1}^{d_v} and m(t)=(m_i(t))_{i=1}^{d_v}; thus u'(t)=(\boldsymbol\phi(m'_i)-\boldsymbol\phi(m_i))_{i=1}^{d_v}. Since \phi is increasing and concave on [0,1/4], its inverse is increasing and convex on [0,\phi(1/4)]. Coordinatewise,

m_i(t,c) \le (1-t)m_i(c)+tm'_i(c)\le B_i, \qquad \sum_c m_i(t,c) \le (1-t)\sum_c m_i(c)+t\sum_c m'_i(c) \le s.

Thus the entire segment lies in \mathcal D_s and satisfies the sharper coordinate bounds needed in Lemma 6.5. The fundamental theorem of calculus and (47) now give

\begin{aligned}w_v\norm{\boldsymbol\phi(m_v)-\boldsymbol\phi(m'_v)}_2 &\le \int_0^1 w_v\norm{\widehat J_v(m(t)) \bigl(u'(t)\bigr)}_2\,dt\\ &\le \rho\max_iw_i\norm{\boldsymbol\phi(m_i)-\boldsymbol\phi(m'_i)}_2.\end{aligned}

If an endpoint has a zero coordinate, approximate it from the relative interior and use continuity.

6.3Total-influence decay and spatial mixing

We first fix the orientation and the messages used in the factorization. Fix a tree \mathcal T=(V_{\mathcal T},E_{\mathcal T}) of maximum degree at most \Deg, a set \Lambda\subseteq V_{\mathcal T}, a pinning \tau\colon\Lambda\to\colours, and a root r\in V_{\mathcal T}\setminus\Lambda. Let \mathcal T_\tau be the component of r in \mathcal T-\Lambda, and let \operatorname{dist}_{\mathcal T_\tau} denote its graph distance. Root \mathcal T_\tau at r. For every y\in V(\mathcal T_\tau)\setminus\{r\}, let y^- be its parent and let \mathcal T_{y\to y^-} be the component containing y after the edge yy^- is removed from \mathcal T_\tau. Write

p_{y\to y^-}

for the cavity marginal of y in this component, including all fixed pinnings incident to vertices of the component, and put m_{y\to y^-}=sp_{y\to y^-}. At the root, p_r is instead the ordinary marginal in the full rooted component and m_r=sp_r. Thus the root object is not being asserted to satisfy the non-root marginal bound. By Lemma 6.3, every cavity message m_{y\to y^-} does satisfy

0\le m_{y\to y^-}(c)\le\frac14, \tag{54}

because deleting the parent edge leaves at most \Deg-1 child and pinned constraints at y.

For a parent y and its free child w, let J_{y,w} denote the block Jacobian, in the potential \psi_s(p)=\phi(sp), of the appropriate oriented update with respect to the incoming message from w: it outputs the full marginal p_r when y=r, and it outputs the cavity marginal p_{y\to y^-} when y\ne r. In the scaled coordinate this is one block of \widehat J_y when y\ne r, and is then controlled by Lemma 6.5; the root block is handled below. Define, with the same distinction between the root and non-root messages,

D_r=\operatorname{diag}\bigl(p_r\psi_s'(p_r)\bigr) =\operatorname{diag}\frac{\sqrt{m_r}}{1-m_r}, \qquad D_{y\to y^-} =\operatorname{diag}\frac{\sqrt{m_{y\to y^-}}} {1-m_{y\to y^-}} . \tag{55}

Products such as p_r\psi_s'(p_r) are coordinatewise. Let I_q denote the q-by-q identity matrix and \mathbf1_q\in\mathbb R^q the all-ones column vector.

Lemma 6.7 (Bounded root response). For every free child u of the root,

D_r^{-1}J_{r,u} =-\bigl(I_q-\mathbf1_qp_r^{\mathsf T}\bigr) \operatorname{diag}\bigl(\sqrt{m_{u\to r}}\bigr), \qquad \norm{D_r^{-1}J_{r,u}}_{2\to2} \le K_q:=\frac{1+\sqrt q}{2}. \tag{56}

Thus the first influence factor is bounded without a lower bound on any coordinate of p_r.

Proof. The raw derivative of (36) is

\frac{\partial p_r(c)}{\partial p_{u\to r}(b)} =\frac{s p_r(c) [p_r(b)-\one{b=c}]}{1-m_{u\to r}(b)}, \qquad \psi_s'(p_{u\to r}(b))^{-1} =\frac{\sqrt{m_{u\to r}(b)} (1-m_{u\to r}(b))}{s}.

The factor p_r(c) cancels against D_r^{-1} before any norm is taken, giving the displayed identity. By (54), \norm{\operatorname{diag}\sqrt{m_{u\to r}}}_{2\to2}\le1/2, while \norm{I_q-\mathbf1_qp_r^{\mathsf T}}_{2\to2}\le1+\sqrt q.

For this pinning \tau\colon\Lambda\to\colours, write \mu_v^\tau for the one-site marginal at a free vertex v under the corresponding tree Gibbs law and \mu_v^{\tau^{r=a}} for that marginal after additionally pinning a free vertex r to a. For distinct free vertices r,v, let \Psi_{r,v} be the q-by-q influence block

\Psi_{r,v}(a,c) :=\mu_v^{\tau^{r=a}}(c)-\mu_v^\tau(c);

we suppress its dependence on \tau. If deleting the vertices pinned by \tau separates r from v, this block is zero. Define the level-\ell total influence by

\mathcal I_\ell(r;\tau) :=\max_{a,b\in\colours} \sum_{\substack{v\in V(\mathcal T_\tau)\\ \operatorname{dist}_{\mathcal T_\tau}(r,v)=\ell}} \norm{\mu_v^{\tau^{r=a}}-\mu_v^{\tau^{r=b}}}_{\rm TV}. \tag{57}

If r and v remain connected, let their free path be

r=u_0,u_1,\ldots,u_\ell=v.

The influence/Jacobian identity of [CLMM23, Lemma 8.7], applied in the successive rooted subtrees, gives

\Psi_{r,v} =D_r^{-1}J_{u_0,u_1} \Bigl(\prod_{j=1}^{\ell-1}J_{u_j,u_{j+1}}\Bigr) D_{v\to u_{\ell-1}} \bigl(I_q-\mathbf1_qp_{v\to u_{\ell-1}}^{\mathsf T}\bigr). \tag{58}

The product is ordered away from the root, is empty when \ell=1, and the intermediate diagonal matrices telescope. The terminal factors use the cavity law in \mathcal T_{v\to u_{\ell-1}}. The identity is exact, and Lemma 6.7 shows that its first factor extends boundedly to a zero root coordinate.

Lemma 6.8 (Tree total-influence decay). Uniformly over 0<x<1, every tree \mathcal T=(V_{\mathcal T},E_{\mathcal T}) of maximum degree at most \Deg, every pinning \tau\colon\Lambda\to\colours with \Lambda\subseteq V_{\mathcal T}, every root r\in V_{\mathcal T}\setminus\Lambda, and every integer \ell\ge1 satisfy

\mathcal I_\ell(r;\tau) \le C_0\rho^{\ell-1} =C_{\rm TID}\rho^\ell, \tag{59}

where one may take

C_0=\frac{\Deg e^{1/12}\sqrt q(1+\sqrt q)^2}{3}, \qquad C_{\rm TID}=\frac{C_0}{\rho}. \tag{60}

The level sum ranges only over free vertices. No positive lower bound on a one-site marginal enters this constant.

Proof. The first factor is bounded by Lemma 6.7; it need not contract. At the terminal end, (54) applies to m_{v\to u_{\ell-1}}, and therefore

\norm{D_{v\to u_{\ell-1}} (I_q-\mathbf1_qp_{v\to u_{\ell-1}}^{\mathsf T})}_{2\to2} \le\frac{2(1+\sqrt q)}3, \tag{61}

because \norm{D_{v\to u_{\ell-1}}}_{2\to2}\le2/3 and \norm{I_q-\mathbf1_qp_{v\to u_{\ell-1}}^{\mathsf T}}_{2\to2}\le1+\sqrt q.

We now use (58) simultaneously over a level. If the level contains no free vertex, the claimed influence bound is immediate. Otherwise, group the terminals by their first child of r, keep the corresponding first factor (56) intact, and peel the remaining \ell-1 levels with the block norm of Lemma 6.5. Every update peeled in this way is a non-root cavity update. Iterating the weighted inequality gives \rho^{\ell-1}; the ratio between its terminal and initial weights is at most e^{1/12} by (48). Finally sum the at most \Deg first-child blocks by the triangle inequality. Thus, for arbitrary terminal block vectors h_v\in\mathbb R^q,

\frac{ \norm{\sum_{\operatorname{dist}_{\mathcal T_\tau}(r,v)=\ell} \Psi_{r,v}h_v}_2} {\max_v\norm{h_v}_2} \le \Deg e^{1/12}K_q\frac{2(1+\sqrt q)}3\rho^{\ell-1}.

Here the product and the contraction exponent are interpreted as empty and 1, respectively, when \ell=1. The standard block L^2-to-L^\infty duality conversion costs at most \sqrt q. Indeed, if

\mathcal A(h):= \sum_{\operatorname{dist}_{\mathcal T_\tau}(r,v)=\ell} \Psi_{r,v}h_v ,

the triangle inequality through the unconditioned law makes the two factors 1/2 in total variation cancel, and hence

\mathcal I_\ell(r;\tau) \le \max_a \sum_{\operatorname{dist}_{\mathcal T_\tau}(r,v)=\ell}\sum_c \abs{\Psi_{r,v}(a,c)} \le \sup_{\max_v\norm{h_v}_\infty\le1}\norm{\mathcal A(h)}_\infty \le \sqrt q\, \sup_{\max_v\norm{h_v}_2\le1}\norm{\mathcal A(h)}_2 .

Using the definition of K_q and writing \rho^{\ell-1}=\rho^{-1}\rho^\ell gives exactly (59)–(60).

Uniform relative SSM cannot start at distance one. Indeed, on a single edge, compare boundary colours a and b\ne a. The probability that the free endpoint has colour a is respectively

\frac{x}{q-1+x} \qquad\text{and}\qquad \frac1{q-1+x},

so the ratio is x (or 1/x in the reverse comparison). The large-girth transfer only needs a relative estimate beyond a fixed depth.

Lemma 6.9 (Relative SSM beyond a fixed depth). For

C_{\rm rel}:=\frac58\Deg q\,e^{1/12}\log3, \tag{62}

the following holds for every 0<x<1 on every tree \mathcal T=(V_{\mathcal T},E_{\mathcal T}) of maximum degree at most \Deg. Fix \Lambda\subseteq V_{\mathcal T}, a pinning \tau\colon\Lambda\to\colours, and a root v\in V_{\mathcal T}\setminus\Lambda. For an integer K\ge2, let

S_K(v):= \{u\in V_{\mathcal T}: \operatorname{dist}_{\mathcal T}(u,v)=K\},

and let

\omega,\omega'\colon S_K(v)\setminus\Lambda\longrightarrow \colours

be two assignments of all unpinned shell vertices. Thus \tau\cup\omega and \tau\cup\omega' are the unions of partial maps with disjoint domains. The two systems have the same fixed pinning \tau and differ only on the shell. Write

p_v:=\mu_v^{\tau\cup\omega}, \qquad p'_v:=\mu_v^{\tau\cup\omega'}.

Here each right-hand side denotes the one-site marginal at v under the indicated pinning. Then, for every root colour c,

\left|\log\frac{p_v(c)}{p'_v(c)}\right| \le C_{\rm rel}\rho^{K-2}. \tag{63}

Define

K_1:=\min\{K\in\mathbb Z_{\ge2}:C_{\rm rel}\rho^{K-2}\le1\}.

For every integer K\ge K_1, the ratio-form relative-SSM error is at most 2C_{\rm rel}\rho^{K-2}. The case x=0 will be added after the final coupling bound by finite-state continuity; at x=1 the left side is zero.

Proof. The pinned children adjacent to the root belong to the fixed pinning \tau, so their colour weights a_v(c) agree. Write

P_c=\prod_i(1-m_i(c)),\qquad p_v(c)=\frac{a_v(c)P_c}{Z},\qquad Z=\sum_b a_v(b)P_b,

and use primes for the second condition. The potentially tiny root colour weight cancels exactly:

\log\frac{p_v(c)}{p'_v(c)} =\log\frac{P_c}{P'_c}+\log\frac{Z'}Z. \tag{64}

Because K\ge2, every message entering the root is the output of a non-root recursion and hence is bounded by 1/4. Therefore

\left|\log\frac{P_c}{P'_c}\right| \le\frac43\sum_i|m_i(c)-m'_i(c)|.

Moreover telescoping the products gives |Z-Z'|\le\sum_i\norm{m_i-m'_i}_1, while the root version of (40) gives Z,Z'\ge3. Consequently

\left|\log\frac{p_v(c)}{p'_v(c)}\right| \le\frac53\sum_i\norm{m_i-m'_i}_1. \tag{65}

The update adjacent to the shell is not compared by a Jacobian, because its local colour weights may change with the shell assignment. Its two output messages nevertheless obey Lemma 6.3. For 1\le j\le K-1, let \mathcal F_j be the free vertices at distance j from v in the same component after the vertices pinned by \tau are deleted. Orient this component toward v, and write y^- for the parent of y. Let

E_j:= \max_{y\in\mathcal F_j} w_y\norm{\boldsymbol\phi(m_{y\to y^-}) -\boldsymbol\phi(m'_{y\to y^-})}_2 .

We set the maximum over an empty set to zero. The potential diameter and (48) give

E_{K-1}\le e^{1/12}\sqrt q\,\phi(1/4) =e^{1/12}\sqrt q\log3.

The two boundary assignments pin the same set of shell vertices, so the two recursions have the same d_y,k_y,B_y,w_y. Every update strictly inside that shell has the same local colour weights on both sides. Thus Lemma 6.6 gives

E_j\le\rho E_{j+1} \qquad(1\le j\le K-2).

These are exactly K-2 contracting levels. Since w_i\ge1 and \inf_{[0,1/4]}\phi'=8/3, Cauchy–Schwarz gives, for each message entering the root,

\norm{m_i-m'_i}_1 \le\frac38\sqrt q\, \norm{\boldsymbol\phi(m_i)-\boldsymbol\phi(m'_i)}_2 \le\frac38q\,e^{1/12}\log3\,\rho^{K-2}.

Summing over at most \Deg root children in (65) proves (63) with (62).

To convert this logarithmic estimate to the relative-error form of [CLMM23, Definition 5.7], put \varepsilon_K:=C_{\rm rel}\rho^{K-2}. By the definition of K_1, for K\ge K_1,

\left|\frac{p_v(c)}{p'_v(c)}-1\right| \le e^{\varepsilon_K}-1\le2\varepsilon_K .

Thus the usual relative-SSM estimate holds uniformly at every K\ge K_1; no assertion is made at distance one.

6.4Transfer to large-girth graphs

The transfer of [CLMM23] still applies when relative SSM begins at a fixed depth K_0.

Lemma 6.10 (Large-girth transfer from tree decay). Let q\ge1 and \Deg\ge3 be integers, and let J\subseteq(0,1]. Suppose there are 0<C_{\mathsf{INFL}},C_{\mathsf{SM}}<\infty, \delta\in(0,1), and a fixed positive integer K_0 such that, for every x\in J and uniformly over all trees T\in\Gdeg, all pinnings \tau of T, and all free roots, the Potts law \mupin{T}{\tau}{x} has level-\ell tree total influence at most C_{\mathsf{INFL}}(1-\delta)^\ell for every integer \ell\ge1, and relative SSM in the ratio sense of [CLMM23, Definition 5.7] at distance K at most C_{\mathsf{SM}}(1-\delta)^K for every integer K\ge K_0. Then there are constants g_{\mathsf{tr}}\in\mathbb Z_{\ge3} and C_{\mathsf{tr}}\ge0, depending only on q,\Deg,C_{\mathsf{INFL}},C_{\mathsf{SM}},\delta,K_0, and in particular not on x or J, with the following property. For every x\in J, every G\in\Gdeg, every pinning \tau with \operatorname{girth}(G^\tau)\ge g_{\mathsf{tr}}, every free source vertex u\in V^\tau, and all b,c\in\colours,

\WHam\!\left( \mupin{G}{\tau^{u=b}}{x}, \mupin{G}{\tau^{u=c}}{x} \right)\le C_{\mathsf{tr}}. \tag{66}

Both laws live on the common free set V^\tau\setminus\{u\}.

Proof. Fix x\in J, and regard each pinned pair (G,\tau) with G\in\Gdeg as a pairwise spin system on its free graph G^\tau, with spin set \colours, the Potts edge factors, and external fields

\lambda_{v,c}=x^{\bcount_v^\tau(c)}.

The family of these systems is closed under further pinnings and deletion of free vertices. Pinning a free vertex r to c removes one free incidence at each neighbour and adds c to its boundary count. Hence, for every remaining vertex v,

\deg_{G^{\tau^{r=c}}}(v) +\sum_d\bcount_v^{\tau^{r=c}}(d) =\deg_{G^\tau}(v)+\sum_d\bcount_v^\tau(d) \le\Deg,

whereas taking a subgraph only lowers this budget. Since x>0, every configuration has positive weight, so every spin is globally feasible after every pinning and the feasibility requirements of the pairwise transfer hold trivially. Conditioning the source u fixes the scalar \lambda_{u,c}, which disappears on normalization, and turns each incident edge into the boundary factor in \tau^{u=c}. Thus the conditional exterior laws supplied by the transfer are exactly the two laws in (66).

The pairwise extension follows from [CLMM23, Remark 5.11], and the relative input is the ratio form in [CLMM23, Definition 5.7]. It remains to check that the proof tolerates the restriction K\ge K_0. The radius, the cutting depth, and the girth bound chosen below depend only on q,\Deg,C_{\mathsf{INFL}},C_{\mathsf{SM}},\delta,K_0, so they serve every x\in J at once.

The cutting depth K is chosen after the influence radius R. The error in the proof of [CLMM23, Lemma 5.14] is

2C_{\mathsf{SM}}(1-\delta)^K\Deg^R +C_{\mathsf{INFL}}(1-\delta)^R. \tag{67}

First choose R, subject to all lower bounds on R in the cited proof, so large that

C_{\mathsf{INFL}}(1-\delta)^R \le\frac1{16R\log\Deg}.

After this R is fixed, choose K subject to all lower bounds on the cutting depth in [CLMM23, Lemmas 5.14 and 5.20], and also

K\ge K_0,\qquad K>R,\qquad K\ge\left\lceil\frac{\log C_{\mathsf{SM}}}{\delta}\right\rceil,\qquad 2C_{\mathsf{SM}}(1-\delta)^K\Deg^R \le\frac1{16R\log\Deg}.

Such a K exists; with this choice (67) is at most 1/(8R\log\Deg), which is the intermediate influence-decay threshold in [CLMM23, Lemma 5.14]. Finally take the girth bound to be the maximum of every girth lower bound in the cited lemmas and 2K+2. Relative SSM is invoked only at this chosen cutting depth, so the restriction K\ge K_0 causes no change later in the argument. Lemmas 5.14 and 5.20 of [CLMM23] therefore supply the intermediate decay condition, and their Lemma 5.13 gives (66) with

C_{\mathsf{tr}}=2\Deg^R.

Proof of Theorem 6.1. Lemmas 6.8 and 6.9 give, for every 0<x<1, tree TID and relative SSM beyond a fixed depth, with constants and rate uniform in x. Apply Lemma 6.10 with

J=(0,1),\qquad C_{\mathsf{INFL}}=C_{\rm TID},\qquad C_{\mathsf{SM}}=2C_{\rm rel}\rho^{-2},\qquad \delta=1-\rho,\qquad K_0=K_1.

It supplies g_{\mathsf{tr}} and C_{\mathsf{tr}}, depending only on (\Deg,q), such that, for every 0<x<1, whenever G^\tau has girth at least g_{\mathsf{tr}},

\WHam\!\left( \mupin{G}{\tau^{r=a}}{x}, \mupin{G}{\tau^{r=b}}{x} \right)\le C_{\mathsf{tr}}. \tag{68}

They live on the common finite state space \colours^{V^\tau\setminus\{r\}}. At x=0, the hypothesis q\ge\Deg+3 implies hard feasibility for every normalized child by Lemma 2.2, so both limiting normalizing constants are positive. Their weights are polynomials in x, and Lemma 3.7 passes the same bound to x=0. At x=1 all remaining spins are independent and the distance is zero. Taking g_*=\max\{3,g_{\mathsf{tr}}\} and C_*=C_{\mathsf{tr}} proves the theorem.

7Coupling independence at high temperature and large girth

This section turns the tree contraction of Bencs, Berrekkal, and Regts [BBR25] into a coupling bound on sufficiently large-girth graphs. The extra step is tree total-influence decay: strong spatial mixing alone does not provide this input to the large-girth transfer of Chen, Liu, Mani, and Moitra [CLMM23].

Fix integers q,\Deg such that

q\ge3,\qquad \frac{\Deg}{q}\ge\frac{e-\frac12}{e-1}. \tag{69}

For (q,\Deg)\ne(3,4), put

k:=e\frac{\Deg-q/2}{\Deg-q}, \qquad x_0:=1-\frac q\Deg \left(1-\frac k\Deg\right)^2 \frac{\Deg-k}{\Deg-k/2}. \tag{70}

For (q,\Deg)=(3,4), put x_0:=3/4. The proof of Theorem 4.6 shows that 0<x_0<1, and that 0<k<\Deg outside the exceptional case. Throughout this section, x\in[x_0,1], and

\kappa:=\frac{\Deg-1}{\Deg}, \qquad \theta:=\sqrt\kappa<1. \tag{71}

Write I_q for the q-by-q identity matrix, \mathbf1_q for the all-ones vector in \mathbb R^q, and e_i for the i-th standard basis vector.

7.1Square-root cavity messages and the BBR certificate

Consider a rooted tree of maximum degree at most \Deg with a fixed pinning \tau. We work in one component of the free graph and represent each free–pinned edge by an individually labelled pinned leaf. Thus the pinning contributes only unary factors at free vertices. For a free non-root vertex v, let T_v be its descendant cavity tree. The numerator Z_{T_v,v=i} below is the restricted partition-function contribution with v=i, retaining the unary factor at v; it is not the normalized child partition function obtained by dropping that scalar. The denominator Z_{T_v-v} deletes v and its incident edges, retaining the unary factors at the remaining vertices. Define

R_v(i):=\left( \frac{Z_{T_v,v=i}(x)}{Z_{T_v-v}(x)} \right)^{1/2}, \qquad i\in\colours. \tag{72}

We use the same ratio at the global root. All entries are positive because x\ge x_0>0. For y\in\mathbb R_{>0}^q, write

S(y):=\sum_i y_i^2,\qquad S_i(y):=S(y)-(1-x)y_i^2,\qquad F_x(y)_i:=\sqrt{\frac{S_i(y)}{S(y)}}. \tag{73}

If \mathcal F_u is the set of free children of u, put f_u:=|\mathcal F_u|. The recursion is

R_u=B_u\odot\prod_{v\in\mathcal F_u}F_x(R_v), \tag{74}

where B_u(i)=x^{\bcount_u^\tau(i)/2} is the product of the square-root unary factors from pinned children. The symbol \odot denotes coordinatewise multiplication, and all products and quotients of vectors in this recursion are coordinatewise.

For two positive messages R,R', let R_t=tR+(1-t)R' and set

L_x(R,R'):= \max_{\substack{0\le t\le1\\ i\in\colours}} \frac{\sqrt{S(R_t)}}{S_i(R_t)}. \tag{75}

A pair is called jointly realizable when its two messages arise at the same cavity vertex of the same rooted tree, with the same pinned domain, after assigning possibly different colours on that domain. This same-tree, same-domain restriction is part of the statement below; no claim is made for arbitrary positive vectors.

Lemma 7.1 (BBR contraction certificate). Let u be a free non-root cavity vertex with f\le\Deg-1 free child branches. For every x\in[x_0,1] and every jointly realizable pair R,R' at u at activity x whose two boundary assignments agree on all pinned vertices at distance at most one from u,

f\,\frac{1-x}{e}\,L_x(R,R')^2\le\kappa. \tag{76}

The empty disagreement set is interpreted as having distance +\infty. Equivalently, the hypothesis is that the nearest changed pin has distance strictly larger than one from u. This is the distance condition in the BBR lower-bound lemma used below. In particular, at a vertex whose nearest changed pin is at distance at least two, the local pinned factor B_u is the same on the two sides, so the finite-difference recursion may use this certificate there.

Proof. Set d=\Deg-1. If x=1, then the left side of (76) is zero, so the claim is immediate; hence assume x<1 in the remainder. First suppose (q,\Deg)\ne(3,4). The ratio hypothesis and integrality then imply \Deg\ge q+2, and hence d\ge q+1. Although Proposition 2.6 of Bencs, Berrekkal, and Regts [BBR25] states the stronger hypothesis d\ge q+2 for its two conclusions together, the estimate in part (i) only invokes their Lemmas 4.3, 4.4, and 4.6 and Corollary 4.5(i). The hypotheses printed with those results are respectively x\in(0,1), q\ge3 and d\ge q+1 (for Lemma 4.4), the distance condition in Lemma 4.6, and q\ge3, d\ge q+1 (for Corollary 4.5(i)); part (ii) of the corollary, which is the place where BBR require d\ge q+2, is not used here. Thus the following extraction of the proof of Proposition 2.6(i) is valid for d\ge q+1. In the notation of their (2.13), put

\alpha:=\frac{(1-x)\Deg}{q}, \qquad\text{so that}\qquad x=1-\alpha q/\Deg.

Their calculation then gives, for 0\le f\le d, the upper bound

\frac{\alpha f}{e\Deg} \left(1-\frac k\Deg\right)^{-2} k^{(d-f)/d} \left(e\frac{\Deg-k/2}{\Deg-k}\right)^{f/d}.

For completeness, this expression is at most its value at f=d. Indeed, writing t=f/d and B=e(\Deg-k/2)/(\Deg-k), the ratio to the f=d value is t(k/B)^{1-t}. The ratio assumption gives k\le e^2 (the function a\mapsto e(a-1/2)/(a-1) is decreasing and equals e^2 at a=(e-1/2)/(e-1)). Therefore

\frac{B}{k}=\frac{e}{k}\,\frac{\Deg-k/2}{\Deg-k} \ge \frac{e}{k}\ge e^{-1}.

Since \log t\le t-1 for 0<t\le1, we have t(k/B)^{1-t}\le t e^{1-t}\le1 (the case f=0 is immediate). Consequently the preceding bound is at most

\frac{\alpha d}{\Deg} \left(1-\frac k\Deg\right)^{-2} \frac{\Deg-k/2}{\Deg-k}.

For x\ge x_0, (70) gives

\alpha\le \left(1-\frac k\Deg\right)^2 \frac{\Deg-k}{\Deg-k/2}.

The preceding bound is therefore at most d/\Deg=(\Deg-1)/\Deg=\kappa.

It remains to treat (q,\Deg)=(3,4), so d=3 and \kappa=3/4. Every coordinate of a cavity message is a product of at most three factors from [\sqrt{x},1]. Hence, along the segment between two realizable messages,

S(R_t)\ge3x^3, \qquad S_i(R_t)\ge xS(R_t), \qquad L_x(R,R')^2\le\frac1{3x^5}.

Consequently, for x\ge x_0=3/4 and f\le3,

f\frac{1-x}{e}L_x(R,R')^2 \le\frac{1-x}{ex^5} \le\frac{256}{243e}<\frac34=\kappa.

The cited BBR bounds, as well as the direct exceptional-case estimate, apply to messages produced by the same cavity tree under two boundary assignments on the same domain, which is exactly the realizability convention above.

7.2Differential contraction

Let H_u denote the local map in (74), and let J_{u\leftarrow v} be its Jacobian block with respect to the message of the free child v. Define the pointwise weight

\ell_x(R):=L_x(R,R) =\max_i\frac{\sqrt{S(R)}}{S_i(R)}, \qquad a_v:=\frac{1-x}{e}\ell_x(R_v)^2. \tag{77}

Lemma 7.2 (Differential contraction). At every collection of child messages arising at a vertex u of a pinned rooted tree at activity x, and for arbitrary vectors z_v\in\mathbb R^q,

\left\|\sum_{v\in\mathcal F_u}J_{u\leftarrow v}z_v\right\|_2^2 \le\sum_{v\in\mathcal F_u}a_v\norm{z_v}_2^2. \tag{78}

In particular, if R_v arises as a non-root cavity message and f_v is the number of free children of v, then

f_va_v\le\kappa. \tag{79}

Proof. Put

P_v:=I_q-\frac{R_vR_v^{\mathsf T}}{S(R_v)}.

Differentiating (73) gives

DF_x(y)= \operatorname{diag}\!\left( \frac{x-1}{F_x(y)}\odot\frac{y}{S(y)} \right) \left(I_q-\frac{yy^{\mathsf T}}{S(y)}\right).

Writing Y=H_u((R_v)_v), the product rule therefore gives

\left(\sum_vJ_{u\leftarrow v}z_v\right)_i =Y_i\sum_v(x-1)\frac{R_v(i)}{S_i(R_v)}(P_vz_v)_i. \tag{80}

Set

\xi_v=\ell_x(R_v)P_vz_v, \qquad h_v(i)=Y_i(1-x) \frac{R_v(i)}{\ell_x(R_v)S_i(R_v)}.

Since \ell_x(R_v)S_i(R_v)\ge\sqrt{S(R_v)} and every coordinate of B_u is at most one,

\sum_vh_v(i)^2 \le \left[\prod_vF_x(R_v)_i^2\right](1-x)^2 \sum_v\frac{R_v(i)^2}{S(R_v)}.

With t_v=(1-x)R_v(i)^2/S(R_v), the right side is (1-x)\prod_v(1-t_v)\sum_vt_v\le(1-x)/e. Coordinatewise Cauchy–Schwarz in (80), followed by \norm{P_v}_{2\to2}\le1, now yields

\left\|\sum_vJ_{u\leftarrow v}z_v\right\|_2^2 \le\frac{1-x}{e}\sum_v\norm{\xi_v}_2^2 \le\sum_va_v\norm{z_v}_2^2.

Finally, apply Lemma 7.1 to the identical pair (R_v,R_v) to obtain (79).

7.3Cavity derivatives and influence

Fix a tree of maximum degree at most \Deg with pinning \tau, and let \mu_v^\tau denote the one-site marginal at a free vertex v. Root the free component containing a free vertex r, and, for every other free vertex v in that component, write

\Psi_{r,v}(b,j) :=\mu_v^{\tau^{r=b}}(j)-\mu_v^\tau(j)

for the q-by-q influence block. In this and the next subsection, distances are measured in the underlying tree. A vertex separated from r by the fixed pinning has zero influence. For every free v in the rooted component, let D_v:=\operatorname{diag}(R_v), and let

Q_r:=D_r^{-1}-\mathbf1_q\frac{R_r^{\mathsf T}}{S(R_r)}. \tag{81}

For a free path from v to r, let \mathcal J_{r\leftarrow v} be the ordered product of the Jacobian blocks along that path. For a free vertex v outside the component of r, set \Psi_{r,v}=0.

Lemma 7.3 (Influence–Jacobian identity). For every free vertex v\ne r in the component of r,

\Psi_{r,v}=Q_r\mathcal J_{r\leftarrow v}D_v. \tag{82}

Consequently, for every integer \ell\ge1, if vectors z_v\in\mathbb R^q are placed on the free vertices in this component at distance \ell from r, set y_v=D_vz_v there and propagate upward by

y_u=\sum_{v\in\mathcal F_u}J_{u\leftarrow v}y_v. \tag{83}

At each preceding level, take this sum over the branches meeting the sphere; an empty sum is zero. Then

\sum_{\substack{\dist(r,v)=\ell\\v\text{ in the component of }r}} \Psi_{r,v}z_v=Q_ry_r. \tag{84}

Proof. Multiply the weight of a configuration by

\exp\!\left( t\sum_{\substack{\dist(r,v)=\ell\\v\text{ in the component of }r}} z_v(\sigma_v)\right).

Write R_v(t) and p_r(\cdot;t) for the cavity messages and root marginal under this reweighted law, and use a dot for differentiation with respect to t at zero. No two vertices on this sphere are ancestors of one another. Hence, at a sphere vertex v,

\dot R_v(0)=\tfrac12D_vz_v.

The chain rule through (74) gives \dot R_r(0)=y_r/2. Since the root marginal is p_r(i)=R_r(i)^2/S(R_r),

d\log p_r=2Q_r\,dR_r.

Thus

\left.\frac d{dt}\log p_r(b;t)\right|_{t=0}=(Q_ry_r)_b. \tag{85}

Differentiating the Gibbs law directly gives the covariance identity

\left.\frac d{dt}\log p_r(b;t)\right|_{t=0} =\sum_{\substack{\dist(r,v)=\ell\\v\text{ in the component of }r}}\sum_j \bigl(\mu_v^{\tau^{r=b}}(j)-\mu_v^\tau(j)\bigr)z_v(j).

Comparison with (85), for arbitrary (z_v)_v, proves both displayed identities.

7.4Tree total-influence decay

Every non-root message contains at most \Deg-1 child factors, each in [\sqrt{x},1]. Uniformly for x\in[x_0,1],

x_0^{\Deg-1}\le R_v(i)^2\le1,\qquad S_i(R_v)\ge x_0S(R_v),\qquad S(R_v)\ge qx_0^{\Deg-1}. \tag{86}

It follows that

a_v\le A:=\frac{1-x_0}{e\,q\,x_0^{\Deg+1}}. \tag{87}

At the global root there are at most \Deg factors, so

\norm{Q_r}_{2\to2} \le\norm{D_r^{-1}}_{2\to2} +\frac{\sqrt q}{\sqrt{S(R_r)}} \le2x_0^{-\Deg/2}. \tag{88}

Proposition 7.4 (Tree total-influence decay). For every tree of maximum degree at most \Deg, every pinning \tau, every free root r, all b,c\in\colours, every x\in[x_0,1], and every integer \ell\ge1,

\sum_{\substack{v:\,\dist(r,v)=\ell\\v\text{ free}}} \norm{\mu_v^{\tau^{r=b}}-\mu_v^{\tau^{r=c}}}_{\rm TV} \le C_0\theta^{\ell-1}, \tag{89}

where

C_0:=\sqrt{\frac{2\Deg(1-x_0)}e}\, x_0^{-(\Deg+1/2)}. \tag{90}

Thus the tree TID hypothesis of Lemma 6.10 holds with C_{\mathsf{INFL}}=C_0/\theta and decay factor \theta.

Proof. If the level contains no free vertex, the claim is immediate. Otherwise, fix vectors z_v on the free part of the level and put M=\max_v\norm{z_v}_2. Propagate the vectors y by (83). At distance \ell-1 from the root, Lemma 7.2, (87), and \norm{D_v}_{2\to2}\le1 give

\frac{\norm{y_u}_2^2}{f_u}\le AM^2 \tag{91}

whenever the subtree below u meets the perturbed sphere. At each higher non-root vertex, every child v carrying a nonzero perturbation has f_v\ge1, and (78)–(79) give

\frac{\norm{y_u}_2^2}{f_u} \le\kappa \max_{v:\,y_v\ne0}\frac{\norm{y_v}_2^2}{f_v}.

At the root we do not divide by its number of children; there are at most \Deg of them. Hence

\norm{y_r}_2\le\sqrt{\Deg A}\,\theta^{\ell-1}M. \tag{92}

For \ell=1, this is the direct estimate from (78) and (87).

Combining (84), (88), and (92) yields

\left\|\sum_{\substack{\dist(r,v)=\ell\\v\text{ free}}} \Psi_{r,v}z_v\right\|_2 \le2\sqrt{\frac{\Deg(1-x_0)}{e\,q}}\, x_0^{-(\Deg+1/2)}\theta^{\ell-1}M. \tag{93}

For b=c the claim is immediate. Otherwise fix b\ne c and take

z_v(j)=\operatorname{sgn}\!\left( \mu_v^{\tau^{r=b}}(j)-\mu_v^{\tau^{r=c}}(j) \right).

Then \norm{z_v}_2\le\sqrt q, while

\sum_{\substack{v:\,\dist(r,v)=\ell\\v\text{ free}}} \norm{\mu_v^{\tau^{r=b}}-\mu_v^{\tau^{r=c}}}_1 =(e_b-e_c)^{\mathsf T} \sum_{\substack{v:\,\dist(r,v)=\ell\\v\text{ free}}} \Psi_{r,v}z_v.

Use \norm{e_b-e_c}_2=\sqrt2, apply (93), and divide by two to obtain (89).

7.5Spatial mixing and transfer to large-girth graphs

The same BBR certificate was designed to control finite differences. We record the precise uniform consequence needed below.

Lemma 7.5 (Uniform relative SSM). Fix x\in[x_0,1]. Let two boundary assignments on a tree of maximum degree at most \Deg have the same pinned domain, and suppose their first possible disagreement from a free root r is at integer distance K\ge2. If p_r,p'_r are the two root marginals and R_r,R'_r their corresponding messages, then

\norm{R_r-R'_r}_2^2\le\Deg q\,\kappa^{K-2}. \tag{94}

Consequently, for every i\in\colours,

\left|\frac{p_r(i)}{p'_r(i)}-1\right| \le C_{\mathsf{SM}}\theta^K, \qquad C_{\mathsf{SM}} :=4q\sqrt{\Deg q}\,x_0^{-3\Deg/2}\kappa^{-1}. \tag{95}

Proof. The finite-difference inequality of [BBR25, Theorem 2.5] is the analogue of (78) with \ell_x(R_v) replaced by the segment weight L_x(R_v,R'_v). For K=2, the crude bound \norm{R_r-R'_r}_2^2\le q is already at most the right side of (94). Now let K\ge3. At distance K-2 from the root, initialize with

\frac{\norm{R_u-R'_u}_2^2}{f_u}\le q.

Indeed, every message that differs there has a free child branch carrying the disagreement, so f_u\ge1. At every vertex contracted above this level, the nearest changed pin is at distance at least two; hence its local pinned factor B_u agrees on the two sides. The branch-normalized finite-difference induction gives a factor \kappa at each of the K-3 non-root levels, and the final root estimate contributes at most \Deg\kappa. This proves (94). The same-tree, same-domain quantifiers are exactly those of Lemma 7.1.

For completeness, every coordinate of a root message satisfies R_r(i)^2\ge x_0^\Deg, and S(R_r)\le q. Thus p_r(i)\ge x_0^\Deg/q. Along the segment between R_r and R'_r,

\left\|\nabla\log\frac{y_i^2}{S(y)}\right\|_2 \le\frac2{y_i}+\frac2{\sqrt{S(y)}} \le4x_0^{-\Deg/2}.

It follows from (94) that

\left|\log\frac{p_r(i)}{p'_r(i)}\right| \le4\sqrt{\Deg q}\,x_0^{-\Deg/2}\kappa^{-1}\theta^K.

If this last bound is at most one, use e^t-1\le2t. Otherwise its being larger than one implies C_{\mathsf{SM}}\theta^K\ge qx_0^{-\Deg}, which covers the crude bound \abs{p_r(i)/p'_r(i)-1}\le qx_0^{-\Deg}. This proves (95).

Theorem 7.6 (BBR-certified interval at large girth). Under (69), there exist g_{\rm BBR}=g_{\rm BBR}(q,\Deg)\ge3 and C_{\rm BBR}=C_{\rm BBR}(q,\Deg)<\infty with the following property. For every G\in\Gdeg, every pinning \tau for which \operatorname{girth}(G^\tau)\ge g_{\rm BBR}, every free vertex r\in V^\tau, all b,c\in\colours, and every x\in[x_0,1],

\WHam\!\left( \mupin{G}{\tau^{r=b}}{x}, \mupin{G}{\tau^{r=c}}{x} \right)\le C_{\rm BBR}. \tag{96}

The two laws are on the common free set V^\tau\setminus\{r\}.

Proof. Consider all normalized pinned Potts systems with activity x\in[x_0,1] and degree budget at most \Deg. On the free graph, a boundary multiplicity \bcount_v^\tau(i) contributes the positive unary factor x^{\bcount_v^\tau(i)}; equivalently, these are the pinned-leaf factors used in (74). Since x_0>0, this is the family of pinned Potts laws in Lemma 6.10 with J=[x_0,1].

Proposition 7.4 and Lemma 7.5 give the two tree inputs to Lemma 6.10, uniformly over the whole interval, with

C_{\mathsf{INFL}}=C_0/\theta,\qquad \delta=1-\theta,\qquad K_0=2,

and C_{\mathsf{SM}} as in (95). That lemma, which incorporates all cutting-depth requirements from the cited large-girth transfer, supplies constants g_{\rm BBR} and C_{\rm BBR}. Its conditional exterior laws are exactly the two normalized child laws in (96), proving the theorem.

8Coupling independence for Edge-Potts at q\ge3\Deg

For a finite simple graph G=(V,E), edge-colour assignments are vertex colourings of the line graph L(G). An edge-colour pinning \tau:\Lambda\to\colours, with \Lambda\subseteq E, is likewise a vertex-colour pinning of L(G). We write

(\edgegibbs{G}{x})^\tau:=\mupin{L(G)}{\tau}{x}.

The Fisher polynomial of this edge-Potts model is simply the vertex-Potts polynomial on L(G); in particular,

\Zpin{L(G)}{\tau}(z) =z^{m_{L(G)}(\tau)}\nZpin{L(G)}{\tau}(z). \tag{97}

The analytic argument is the vertex-Potts transfer on line graphs; the additional input is the following coupling bound.

Theorem 8.1 (Edge-Potts coupling independence). Let q,\Deg be positive integers with q\ge3\Deg. For every finite simple graph G of maximum degree at most \Deg, every edge-colour pinning \tau, every x\in[0,1], every free edge i\in E\setminus\operatorname{dom}\tau, and all a,b\in\colours, put, for c\in\colours,

\tau^{i=c}:=\tau\cup\{i\mapsto c\}, \qquad (\edgegibbs{G}{x})^{\tau,i=c} :=(\edgegibbs{G}{x})^{\tau^{i=c}}.

Then, on the common free edge set E\setminus(\operatorname{dom}\tau\cup\{i\}),

\WHam\!\left( (\edgegibbs{G}{x})^{\tau,i=a}, (\edgegibbs{G}{x})^{\tau,i=b} \right) \le\Deg-1. \tag{98}

Corollary 8.2 (Edge-Potts zero-freeness). Let q,\Deg be positive integers with \Deg\ge2 and q\ge3\Deg. There exists \eps=\eps(q,\Deg)>0 such that, for every finite simple graph G of maximum degree at most \Deg and every edge-colour pinning \tau,

\nZpin{L(G)}{\tau}(z)\ne0 \qquad\text{whenever }\dist(z,[0,1])<\eps.

Thus the unnormalized pinned polynomial has no zero in this neighbourhood except possibly at z=0; its order of vanishing there is m_{L(G)}(\tau). In particular, Z_{L(G)}(z)\ne0 throughout the same neighbourhood.

Proof. The line graph has maximum degree at most \Deg_L:=2\Deg-2. The class of line graphs of simple graphs of maximum degree at most \Deg is closed under taking induced subgraphs, since an induced subgraph on an edge set S is the line graph of (V,S). Vertex pinnings in this class are exactly edge-colour pinnings, with the normalization in (97). Moreover, q\ge3\Deg implies q\ge\Deg_L+1, and Theorem 8.1 supplies one coupling-independence constant on [0,1]. Apply Theorem 2.4 with degree bound \Deg_L. The statement for the unnormalized polynomial follows from (97).

Proof overview.

For 0<x<1, hidden endpoint slots represent the edge-Potts weight by a hard distinct-label constraint. Replacing one occupied endpoint label admits a coupling with expected Hamming distance at most (\Deg-1)/2; conditioning i requires one replacement at each endpoint. The resulting coupling is a countable weighted adaptation of the list-edge-colouring coupling in [CWZZ25].

8.1Exact slot lift

Fix a finite simple graph G=(V,E) of maximum degree at most \Deg, and q\ge3\Deg. Fix 0<x<1, a subset \Lambda\subseteq E, and an edge-colour pinning \tau\colon\Lambda\to\colours. Thus \operatorname{dom}\tau=\Lambda, and F_0=E\setminus\Lambda is the initial set of free edges. Fix once and for all an ordering e=(e^-,e^+) of the two endpoints of every e\in E. When using slot notation for e, we always write (u,v)=(e^-,e^+), so that e=uv has this fixed ordered meaning. For a vertex v and colour c, write

\bcount_v^\tau(c) :=\abs{\set{e\in\operatorname{dom}\tau:e\ni v,\ \tau(e)=c}},

so here \bcount_v^\tau(c) counts pinned edges incident to the base-graph vertex v. For \phi\colon F_0\to\colours, put

k_{v,c}(\phi) :=\abs{\set{e\in F_0:e\ni v,\ \phi(e)=c}}.

For an edge colouring \psi:D\to\colours, where D\subseteq E, put

\Nconf(\psi) :=\abs{\set{\{e,f\}\subseteq D: e\ne f,\ e\cap f\ne\varnothing,\ \psi(e)=\psi(f)}}.

Then m_{L(G)}(\tau)=\Nconf(\tau). Because G is simple, two distinct edges share at most one endpoint. Consequently,

\Nconf(\tau\cup\phi)-m_{L(G)}(\tau) = \sum_{v,c} \left[ \bcount_v^\tau(c)\,k_{v,c}(\phi) +\binom{k_{v,c}(\phi)}2 \right]. \tag{99}

The two terms count pinned–free and free–free conflicts, respectively; the pinned–pinned conflicts are precisely the subtracted normalization.

The second term in (99) has the following probabilistic representation.

Lemma 8.3 (Slot representation). For every 0<x<1, there is a probability distribution (\kappa_r)_{r\ge1}, with every \kappa_r>0, such that for every integer k\ge0,

\sum_{\substack{r_1,\ldots,r_k\ge1\\ r_1,\ldots,r_k\ {\rm all\ distinct}}} \prod_{j=1}^k \kappa_{r_j} =x^{\binom k2}. \tag{100}

Proof. Define the deformed exponential

\mathcal E_x(t):=\sum_{k\ge0}x^{\binom k2}\frac{t^k}{k!}.

By [MFB72, Ise93], all zeros of \mathcal E_x are real and negative; see also [WZ18, §1, pp. 312–313]. Write them, with multiplicity, as -1/\kappa_r, where \kappa_r>0. If a_k is the coefficient of t^k, then

\log\frac1{\abs{a_k}} =\abs{\log x}\binom k2+\log k!,

so \mathcal E_x is entire of order zero. Its genus-zero Hadamard factorization is

\mathcal E_x(t) =\prod_{r\ge1}(1+\kappa_r t).

There is no exponential factor, and the constant is fixed by \mathcal E_x(0)=1. In particular, \sum_r\kappa_r<\infty, so the product and its coefficient expansions converge absolutely. Comparison of the linear coefficients gives \sum_r\kappa_r=1, and comparison at degree k gives

\sum_{1\le r_1<\cdots<r_k} \kappa_{r_1}\cdots\kappa_{r_k} =\frac{x^{\binom k2}}{k!}.

Multiplication by k! gives (100).

Thus k independent slots with law (\kappa_r) are all distinct with probability x^{\binom k2}. Apply this identity separately at every vertex–colour pair.

For a free edge e=uv, use the lifted state

\xi=(c,r,s)\in\colours\times\mathbb N_{\ge1}^2

with activity

w_e(c,r,s) :=x^{\bcount_u^\tau(c)+\bcount_v^\tau(c)}\kappa_r\kappa_s. \tag{101}

These activities always use the original colour pinning \tau and remain fixed during later lifted-state pinnings; the latter are recorded only in the occupied-label sets defined below. At u this state exposes the endpoint label \ell_{e,u}(\xi)=(c,r), and at v it exposes \ell_{e,v}(\xi)=(c,s). A lifted assignment is admissible when all labels exposed at any one vertex are distinct.

After some lifted edge states have been pinned, let F\subseteq F_0 denote the current free-edge set and let B_v\subseteq \colours\times\mathbb N_{\ge1} be a finite set of occupied labels at v, write B=(B_v)_{v\in V}, and put

\deg_F(v):=\abs{\set{e\in F:v\in e}}.

An assignment

\omega=(\omega_e)_{e\in F} \in\bigl(\colours\times\mathbb N_{\ge1}^2\bigr)^F

on the current free-edge set is admissible when the labels in B_v, together with those exposed by the incident free edges, are pairwise distinct at every v. Its weight is

W_{F,B}(\omega):=\prod_{e\in F}w_e(\omega_e),

and \nu_{F,B} denotes the corresponding normalized law on admissible assignments whenever its partition sum is positive.

For a current free edge e=uv, define

d_F(e) :=\abs{\set{f\in F\setminus\set e:f\cap e\ne\varnothing}}

and let

M_e(B) := \sum_{\substack{\xi=(c,r,s)\\ \ell_{e,u}(\xi)\notin B_u,\; \ell_{e,v}(\xi)\notin B_v}} w_e(\xi)

be the activity compatible with the occupied boundary labels. The required bounds, for every v\in V and e\in F as applicable, are

\begin{align}\deg_F(v)+\abs{B_v}&\le\Deg, \tag{102}\\ \sum_{\xi:\,\ell_{e,y}(\xi)=\zeta}w_e(\xi)&\le1 \quad (y\in e,\ \zeta\in\colours\times\mathbb N_{\ge1}), \tag{103}\\ M_e(B)-d_F(e)&\ge\Deg+2. \tag{104}\end{align}

Pinning an admissible positive-activity state \xi on e=uv produces F'=F\setminus\set e and the occupied-label family B' given by

B'_u=B_u\cup\set{\ell_{e,u}(\xi)},\qquad B'_v=B_v\cup\set{\ell_{e,v}(\xi)},\qquad B'_y=B_y\quad(y\notin\{u,v\}).

Lemma 8.4 (Exact lift and inherited bounds). Assume q\ge3\Deg. For the initial data (F_0,\varnothing), where \varnothing denotes the family of empty occupied-label sets, colour projection (c,r,s)\mapsto c sends the lifted law exactly to the normalized pinned edge-Potts law (\edgegibbs{G}{x})^\tau.

The initial slot instance and every boundary obtained by successively pinning admissible positive-activity states satisfy (102)–(104). More generally, any instance (F,B) with finite occupied-label sets that uses the endpoint-label maps and activities in (101) and satisfies these three bounds has a finite, positive partition sum.

Proof. Fix a colour assignment \phi\colon F_0\to\colours and sum over its slot fibre. The sum factorizes over the pairs (v,c). If k=k_{v,c}(\phi), the activities contribute x^{\bcount_v^\tau(c)k}, while admissibility requires the k endpoint slots to be distinct. By (100), their total slot weight is x^{\binom k2}. Hence the fibre weight is

\prod_{v,c} x^{\bcount_v^\tau(c)k_{v,c}(\phi)+ \binom{k_{v,c}(\phi)}2} = x^{\Nconf(\tau\cup\phi)-m_{L(G)}(\tau)}

by (99). This proves exact projection.

Initially, (102) follows from \deg_{F_0}(v)\le\Deg. For a fixed endpoint label, say (c,r) at u,

\sum_s w_e(c,r,s) = x^{\bcount_u^\tau(c)+\bcount_v^\tau(c)}\kappa_r\sum_s \kappa_s \le1,

and the other endpoint is symmetric. This proves (103).

For the slack, let

\bcount_e:=\sum_c\bigl(\bcount_u^\tau(c)+\bcount_v^\tau(c)\bigr),

the number of pinned edges adjacent to e=uv. Since \sum_r\kappa_r=1,

M_e(\varnothing) =\sum_c x^{\bcount_u^\tau(c)+\bcount_v^\tau(c)} \ge q-\bcount_e.

Here we used x^m\ge1-m for nonnegative integers m and 0<x<1. Simplicity gives

d_{F_0}(e)+\bcount_e = \abs{\set{f\in E\setminus\set e:f\cap e\ne\varnothing}} \le2\Deg-2,

and therefore

M_e(\varnothing)-d_{F_0}(e) \ge q-d_{F_0}(e)-\bcount_e \ge3\Deg-(2\Deg-2)=\Deg+2.

It remains to check one pinning step for current data (F,B). Suppose e is pinned and a remaining edge f meets e. Simplicity makes the common endpoint unique. The new occupied label removes from M_f at most one endpoint fibre, whose activity is at most one by (103); deleting e decreases d_F(f) by exactly one. Thus

M_f(B')-d_{F\setminus\set e}(f) \ge (M_f(B)-1)-(d_F(f)-1) \ge\Deg+2.

Nonadjacent edges are unchanged. At each endpoint of e, the free degree drops by one and one genuinely new occupied label is added, so (102) is preserved. The activities, and hence (103), do not change.

Finally, the three bounds imply feasibility by greedy exposure. At every step an unassigned edge has at least M_e(B)-d_F(e)\ge\Deg+2>0 compatible activity, and the preceding pinning argument preserves the same conclusion. The partition sum is finite because there are finitely many edges and \sum_\xi w_e(\xi)\le q for each edge.

8.2Coupling under a boundary-label replacement

Consider two occupied-label systems with the same free graph, endpoint-label maps, and edge activities. Fix a vertex v, a finite C_v\subseteq\colours\times\mathbb N_{\ge1} and distinct \alpha,\beta\in (\colours\times\mathbb N_{\ge1})\setminus C_v. Their occupied-label families satisfy B_y^\alpha=B_y^\beta for y\ne v, while at v,

B_v^\alpha=C_v\cup\set\alpha, \qquad B_v^\beta=C_v\cup\set\beta.

Both systems satisfy (102)–(104). These three bounds, rather than derivation from the initial lift, are the hypotheses because the two-step comparison uses mixed endpoint boundaries.

For two lifted assignments on F, let

\Ham_F(\omega,\omega') :=\bigl|\{e\in F:\omega_e\ne\omega'_e\}\bigr|,

and write W_{1,F} for the infimum of the expected \Ham_F-cost over couplings of two laws on the resulting countable state space.

For each integer n\ge0, let \mathsf T_n be the supremum of W_{1,F}(\nu_{F,B^\alpha},\nu_{F,B^\beta}) over all data described in the preceding paragraph that satisfy the three displayed bounds and have at most n free edges. The laws exist by Lemma 8.4, 0\le\mathsf T_n\le n, and \mathsf T_0=0.

Lemma 8.5 (One-label coupling bound). One has \mathsf T_0=0, and for every integer n\ge1,

\mathsf T_n \le \frac{\Deg-1}{2} \left[ 1-\left(\frac{\Deg-1}{\Deg}\right)^n \right] \le\frac{\Deg-1}{2}. \tag{105}

Proof. Only n\ge1 requires proof. Fix an admissible comparison with 1\le |F|\le n; the case F=\varnothing has zero cost. Write \mu_\alpha:=\nu_{F,B^\alpha}, \mu_\beta:=\nu_{F,B^\beta}, and let N=\set{j\in F:j\ni v}. Under \mu_\alpha, define

E_j^\beta :=\set{\omega:\ell_{j,v}(\omega_j)=\beta}, \qquad E_0^\beta :=\set{\omega:\text{no edge of $N$ exposes $\beta$ at $v$}}.

Define E_j^\alpha,E_0^\alpha symmetrically under \mu_\beta. Distinctness of endpoint labels makes the label-exposure events (E_j^\beta)_{j\in N} disjoint, and together with E_0^\beta they partition the \alpha-side state space; the same holds on the other side.

The avoidance events have positive probability. Fix either current boundary B\in\{B^\alpha,B^\beta\}. For that side, greedily expose the free edges while additionally forbidding the missing label at v. For an incident edge this removes at most one further endpoint fibre, so the available activity is at least

M_e(B)-d_F(e)-1\ge\Deg+1>0.

At each exposure, deleting the chosen edge lowers the remaining free edge-degrees by the same amount as the new occupied endpoint labels can lower their allowed activities, so this positive margin persists at every later step. Set

\rho_j :=\frac{\mu_\alpha(E_j^\beta)}{\mu_\alpha(E_0^\beta)}, \qquad \sigma_j :=\frac{\mu_\beta(E_j^\alpha)}{\mu_\beta(E_0^\alpha)},

with a zero numerator interpreted as zero.

To bound these label-exposure odds, start from a configuration in E_j^\beta, keep every state off j and replace the state of j by a compatible state that does not expose \beta at v. The other adjacent free edges exclude at most d_F(j) endpoint fibres, and avoiding \beta excludes one more. Thus the replacement activity is at least \Deg+1. Route the source weight among the replacements proportionally to their activities. Conversely, for a fixed target, summing all source states whose endpoint colour is \beta gives total activity x^{\bcount_u^\tau(\beta)+\bcount_v^\tau(\beta)}\le1, which is also the bound supplied by (103). Summing this flow gives

\sum_{\omega\in E_j^\beta}W_{F,B^\alpha}(\omega) \le\frac1{\Deg+1} \sum_{\omega\in E_0^\beta}W_{F,B^\alpha}(\omega),

and hence

\rho_j\le\frac1{\Deg+1}.

The same argument gives \sigma_j\le1/(\Deg+1). Since one boundary label is already occupied at v, (102) implies \abs N\le\Deg-1. Hence

R:=\sum_{j\in N}\max\{\rho_j,\sigma_j\} \le\frac{\Deg-1}{\Deg+1}. \tag{106}

Write

\nu_0^\alpha:=\mu_\alpha(\,\cdot\mid E_0^\beta), \qquad \nu_j^\alpha:=\mu_\alpha(\,\cdot\mid E_j^\beta),

and define \nu_0^\beta,\nu_j^\beta symmetrically. A conditional law with zero coefficient below is omitted. We next record the three conditional comparisons:

\begin{align}W_{1,F}(\nu_0^\alpha,\nu_0^\beta)&=0, \tag{107}\\ W_{1,F}(\nu_j^\alpha,\nu_j^\beta)&\le1+\mathsf T_{n-1}, \tag{108}\\ \max\!\left\{ W_{1,F}(\nu_j^\alpha,\mu_\beta), W_{1,F}(\mu_\alpha,\nu_j^\beta) \right\}&\le1+2\mathsf T_{n-1}. \tag{109}\end{align}

For (107), the two avoidance events produce the same boundary C_v\cup\set{\alpha,\beta}, so the conditional laws are identical.

For the other two bounds, condition further on the complete state of j=vw, remove j, and put its endpoint labels into the boundary. For each pair of conditioned states, the remaining-edge laws are compared through the corresponding residual boundary; mixing these conditional couplings over the state of j preserves the stated uniform cost. For (108), the boundaries at v then agree, and the two systems differ by at most one label replacement at w. The residual cost is at most \mathsf T_{n-1}, and restoring j costs at most one.

For (109), compare the two residual laws through the boundary that uses the first conditioned system’s labels at v and the second conditioned system’s labels at w. This requires at most one label replacement at each endpoint. After j is removed, simplicity ensures that no remaining edge meets both v and w. Every remaining edge therefore sees exactly the endpoint restrictions of one of the two conditioned systems, so the intermediate boundary satisfies (102)–(104) and is feasible. Its residual cost is at most 2\mathsf T_{n-1}, and restoring j again costs at most one. The conditioning mixtures are countable, but all these costs are uniform. For each \eta>0, choose every conditional coupling with expected cost within \eta of its Wasserstein infimum. Tonelli’s theorem, followed by \eta\downarrow0, gives (108)–(109).

It remains to couple the exposure blocks. The following table specifies a nonnegative mixture of couplings. Every displayed mass is divided by 1+R; the first row is used once and the other rows once for each j\in N. Zero-mass rows are omitted, and (t)_+:=\max\{t,0\}:

\begin{array}{c|c|c} \text{numerator}&\alpha\text{-side}&\beta\text{-side}\\ \hline 1&\nu_0^\alpha&\nu_0^\beta\\ \min\{\rho_j,\sigma_j\}&\nu_j^\alpha&\nu_j^\beta\\ (\rho_j-\sigma_j)_+&\nu_j^\alpha&\mu_\beta\\ (\sigma_j-\rho_j)_+&\mu_\alpha&\nu_j^\beta \end{array} \qquad(j\in N).

To check the first marginal, note that

\nu_0^\alpha+\sum_j\rho_j\nu_j^\alpha =\left(1+\sum_j\rho_j\right)\mu_\alpha

and

R=\sum_j\rho_j+\sum_j(\sigma_j-\rho_j)_+.

Thus the rows on the \alpha-side sum to (1+R)\mu_\alpha; the other marginal is symmetric. Combining the table with (107)–(109) gives

\begin{aligned} W_{1,F}(\mu_\alpha,\mu_\beta) &\le \frac{ \sum_j\min\{\rho_j,\sigma_j\}(1+\mathsf T_{n-1}) +\sum_j\abs{\rho_j-\sigma_j}(1+2\mathsf T_{n-1}) }{1+R}\\ &\le \frac{R}{1+R}(1+2\mathsf T_{n-1}) \le \frac{\Deg-1}{2\Deg}(1+2\mathsf T_{n-1}), \end{aligned}

where the last step uses (106). Taking the supremum over all such comparisons gives

\mathsf T_n\le\frac{\Deg-1}{2\Deg}(1+2\mathsf T_{n-1}).

Solving this affine recursion from \mathsf T_0=0 yields (105).

8.3From slot couplings to coupling independence

Proof of Theorem 8.1. If a=b, the two normalized children are identical. Assume a\ne b, and write the root edge as i=uv.

Case x=1. Under every pinning, the remaining edge colours are independent and uniform, so the root-excluded distance is zero.

Case 0<x<1. Construct the single slot lift associated with the original pinning \tau. By Lemma 8.4, its colour projection is exactly (\edgegibbs{G}{x})^\tau. Conditioning the root edge i to colour a disintegrates the lifted child over the positive-mass root states (a,r,s); the b-child is the analogous mixture over (b,r',s'). Both are conditionals of this same lift.

For c\in\{a,b\}, let \Pi_c denote the law of \omega_i under \nu_{F_0,\varnothing}, conditional on the colour coordinate of \omega_i being c. Thus every \xi\in\operatorname{supp}\Pi_c has the form (c,r,s). For such a state \xi, delete i and define the occupied-label family on the remaining system by

B_y^\xi:= \begin{cases} \set{\ell_{i,y}(\xi)},&y\in i,\\ \varnothing,&y\notin i. \end{cases}

Set

\nu^\xi:=\nu_{F_0\setminus\{i\},B^\xi}.

Thus the root-excluded lifted c-child is the \Pi_c-mixture of the laws \nu^\xi.

Fix \xi\in\operatorname{supp}\Pi_a and \xi'\in\operatorname{supp}\Pi_b, and delete i. Each conditioned law satisfies (102)–(104). Compare the two laws through the boundary that takes the first root state’s label at u and the second root state’s label at v. Since G is simple, no remaining edge meets both u and v; hence this intermediate boundary inherits the three bounds from the two conditioned systems. The two comparisons change at most one occupied label each. Therefore

W_{1,F_0\setminus\{i\}}(\nu^\xi,\nu^{\xi'}) \le2\mathsf T_{\abs{F_0}-1}\le\Deg-1

by Lemma 8.5.

Couple the two countable root-state laws by the product law \Pi_a\otimes\Pi_b. For each \eta>0 and every positive-mass pair (\xi,\xi'), choose a coupling of \nu^\xi and \nu^{\xi'} whose expected cost is within \eta of the corresponding Wasserstein infimum, and then let \eta\downarrow0. Tonelli’s theorem preserves the same uniform bound. Colour projection cannot increase Hamming distance, so the two edge-Potts children have root-excluded distance at most \Deg-1.

Case x=0. Work in the finite colour space. Every normalized hard child exists: after fixing i, greedily colour the remaining vertices of the line graph, equivalently the remaining free edges of G. Each sees at most 2\Deg-2 already coloured neighbours, whereas q\ge3\Deg.

For c\in\set{a,b}, put

t_c:=\bcount_u^\tau(c)+\bcount_v^\tau(c).

Then

m_{L(G)}(\tau^{i=c}) =m_{L(G)}(\tau)+t_c,

and for every colouring \phi of the remaining edges and x>0,

\begin{aligned} &x^{\Nconf(\tau^{i=c}\cup\phi) -m_{L(G)}(\tau)}\\ &\qquad = x^{t_c}\, x^{\Nconf(\tau^{i=c}\cup\phi) -m_{L(G)}(\tau^{i=c})}. \end{aligned}

The first factor is independent of \phi, so ordinary conditioning for x>0 is exactly the normalized child. After this scalar is removed, the two families of weights are finite polynomials in x, and their partition sums are positive at x=0 by the preceding greedy argument. Lemma 3.7 therefore passes the bound \Deg-1 to the normalized hard children.

9Coupling independence at girth five for q\ge(1+\delta)\Deg

9.1Proof of coupling independence

The proof combines a two-layer disintegration, a covariance bound for the insertion residual, and a weighted response recursion. The spectral-gap input is proved in Section 9.2.

Throughout this section, q,\Deg are positive integers, 0<\delta\le1, x\in[0,1], and s:=1-x. In this subsection, assume q\ge(1+\delta)\Deg. A residual instance I=(H,\mathbf b) consists of a finite simple free graph H and nonnegative integer boundary counts b_v(c) satisfying

\deg_H(v)+k_H(v)\le\Deg, \qquad k_H(v):=\sum_{c\in\colours}b_v(c). \tag{110}

These counts agree with \bcount_v^\tau(c) from Section 2. Write \mu_I for the normalized Gibbs law at the fixed activity x, \mathbb E_I for its expectation, and p_{I,v} for its marginal at v. The instance I-v deletes v and its incident edges but retains the boundary counts at the remaining vertices; pinning a vertex instead adds the corresponding boundary counts at its free neighbours. For x>0, \mu_{I,w}^{v=c} denotes the marginal at w after conditioning v to colour c. At x=0 it denotes the w-marginal of the normalized child law from Section 2, even when c has zero probability in the parent law. All distances and spheres refer to the stated free graph; in particular, S_2^H(v):=\{w:\dist_H(v,w)=2\}. In colour space, I_q is the identity matrix and \mathbf1\in\mathbb R^q is the all-ones vector.

Set

m:=q-\Deg,\qquad B:=m^{-1},\qquad L_\Deg:=\frac{1+\sqrt{q/(m+1)}}{m}. \tag{111}

The colour hypothesis gives m\ge\delta\Deg; the estimates below include equality throughout. We use the threshold and gap constant

\Deg_0(\delta):=\left\lceil \frac{4096(1+\delta)e^{2/\delta}}{\delta^4}\right\rceil, \qquad \gamma_\delta:=\frac{\delta}{4(2+\delta)}. \tag{112}

We assume \Deg\ge\Deg_0(\delta), so in particular B<1. For a free site w, write \operatorname{Var}_w f:=\operatorname{Var}(f\mid \sigma_{V(H)\setminus\{w\}}) under the current Gibbs law. The spectral-gap input, proved in Theorem 9.7, is

\operatorname{Var}_{\mu_I}(f) \le\frac1{\gamma_\delta}\sum_{w\in V(H)} \mathbb E_{\mu_I}[\operatorname{Var}_w f]. \tag{113}

It applies after every further pinning and deletion that preserves (110) and girth at least five.

Local geometry.

Lemma 9.1 (Second-layer disintegration). Let I=(H,\mathbf b) be a residual instance, let v be free, and put U=N_H(v), S=S_2^H(v), and \nu=\mu_{I-v}. If \operatorname{girth}(H)\ge5, then U is independent, each w\in S has a unique neighbour in U, and, with O=V(H)\setminus(\{v\}\cup U\cup S), the following holds for every \xi with \nu(\sigma_S=\xi)>0:

\nu(d\sigma_U,d\sigma_O\mid\sigma_S=\xi) =\left(\bigotimes_{u\in U}\pi_u^\xi(d\sigma_u)\right) \otimes\nu_O^\xi(d\sigma_O). \tag{114}

Here \pi_u^\xi and \nu_O^\xi are the conditional marginals of \sigma_u and \sigma_O, respectively, under \nu given \sigma_S=\xi. In particular, all edges inside S and all edges inside O are retained; the marginal law on S is not assumed to be a product law.

Proof. There are no edges inside U by the absence of triangles. Every neighbour of u\in U other than v lies in S, and uniqueness follows because two neighbours in U would give a four-cycle through v. After S is fixed, all factors incident with S become unary factors and the remaining Gibbs weight separates into the isolated vertices U and the induced exterior graph O. Normalization gives (114).

The disintegration isolates the neighbours of the root once the second layer is revealed. We next control how changing one second-layer coordinate changes that root-neighbour contribution in the colour direction.

Lemma 9.2 (One-edge colour operator). Assume m\ge\delta\Deg and let r be a cavity colour law obtained after deleting one incident constraint. For h\in\mathbb R^q, define

(T_r h)(t)=\frac{\langle r,h\rangle-sr(t)h(t)}{1-sr(t)}, \qquad t\in\colours.

Then r(c)\le(m+1)^{-1} and, for the Euclidean projection \Pi:=I_q-q^{-1}\mathbf1\mathbf1^{\mathsf T} onto the subspace orthogonal to constants,

\|\Pi T_r\Pi\|_{2\to2}\le L_\Deg.

If the updated one-site law \varrho has atoms at most B, then

\operatorname{Var}_{t\sim\varrho}\bigl((T_rh)(t)\bigr) \le BL_\Deg^2\|h\|_2^2. \tag{115}

The estimate remains valid when h depends on all other coordinates but not on the colour currently updated.

Proof. Writing \vartheta_c:=sr(c)/(1-sr(c)) and \vartheta=(\vartheta_c)_{c\in\colours} gives

T_r=\mathbf1r^{\mathsf T}-\operatorname{diag}(\vartheta) (I_q-\mathbf1r^{\mathsf T}).

The first term vanishes after projection, while \max_c\vartheta_c\le m^{-1} and \|I_q-\mathbf1r^{\mathsf T}\|_{2\to2}\le1+\sqrt{q/(m+1)}. This proves the quotient bound. Finally \operatorname{Var}_{\varrho}(g)=\min_{a\in\mathbb R} \sum_j\varrho_j(g_j-a)^2\le B\|\Pi g\|_2^2, which gives (115).

Colour covariance defect. For the quantitative bounds below set

a_B=(1-B)^{-1},\quad V_\pi=\frac{\Deg B L_\Deg^2}{\gamma_\delta},\quad V_M=\Deg V_\pi,

D_\Deg=\frac{\Deg B^2a_B}{2},\quad E_\Deg=D_\Deg+\tfrac12e^{\Deg B}V_M,\quad b_\Deg=a_B^2\sqrt{V_\pi}+a_Be^{\Deg B+2D_\Deg} (\sqrt{V_M}+D_\Deg),

g_\Deg=\sqrt{V_M}\,b_\Deg,\qquad \ell_\Deg=2\Deg B b_\Deg,\qquad K_\Deg=\Deg g_\Deg,\qquad \widetilde\epsilon_\Deg=\sqrt B\,K_\Deg. \tag{116}

For fixed \delta, these satisfy b_\Deg=O_\delta(\Deg^{-1/2}), g_\Deg=O_\delta(\Deg^{-1}), K_\Deg=O_\delta(1), and \widetilde\epsilon_\Deg=O_\delta(\Deg^{-1/2}).

The next lemma is the key girth-five estimate: the insertion residual has only a small colour-direction covariance, even though the second layer itself need not be a product measure.

Lemma 9.3 (Colour covariance of the insertion residual). Assume 0<\delta\le1, \Deg\ge\Deg_0(\delta), q\ge(1+\delta)\Deg, and 0<x<1. Suppose that every residual instance used below satisfies the degree budget, so that (113) applies. Under the hypotheses of Lemma 9.1, sums and products over neighbours range over U unless stated otherwise. Fix a colour c and put X_{u,c}=\mathbf1_{\{\sigma_u=c\}}, p_{u,c}=\mathbb E_\nu X_{u,c},

F_c=\prod_{u\in U}(1-sX_{u,c}),\quad T_c=\mathbb E_\nu F_c,\quad Q_c=\prod_{u\in U}(1-sp_{u,c}),\quad \alpha_{u,c}=\frac{s}{1-sp_{u,c}}.

Let

R_c=F_c/T_c-1+\sum_u\alpha_{u,c}(X_{u,c}-p_{u,c}), \qquad G_c=\mathbb E_\nu[R_c\mid\sigma_S].

For \beta_{u,c} defined by

\beta_{u,c}=\alpha_{u,c}-\frac{s}{T_c} \prod_{j\ne u}(1-s\pi_{j,c}), \qquad \pi_{u,c}=\mathbb E_\nu[X_{u,c}\mid\sigma_S],

the coefficient \beta_{u,c} does not depend on the configuration \sigma_{W_u}, where W_u=N_H(u)\setminus\{v\}. Moreover, for every deterministic z\in\mathbb R^q,

\operatorname{Var}_w\!\left(\sum_cz_cG_c\right) \le BL_\Deg^2\sum_cz_c^2\beta_{u,c}^2\qquad(w\in W_u). \tag{117}

The insertion-quotient expansion proved below gives \|\beta_{u,c}\|_{L^2(\nu)}\le b_\Deg uniformly in u,c, where b_\Deg=O_\delta(\Deg^{-1/2}). Consequently,

\|\operatorname{Cov}_\nu(G_1,\ldots,G_q)\|_{2\to2} \le V_M b_\Deg^2=:g_\Deg^2, \qquad g_\Deg=O_\delta(\Deg^{-1}). \tag{118}

Write G=(G_c)_{c\in\colours} as a column vector; its covariance matrix has entries \operatorname{Cov}_\nu(G_c,G_d). For every probability vector r with r_c\le B, it follows that

\operatorname{Cov}_\nu(\operatorname{diag}(\sqrt r)G) =\operatorname{diag}(\sqrt r)\operatorname{Cov}_\nu(G)\operatorname{diag}(\sqrt r), \qquad \|\operatorname{Cov}_\nu(\operatorname{diag}(\sqrt r)G)\|_{2\to2} \le Bg_\Deg^2. \tag{119}

Proof. The affine formula for G_c gives the stated expression for \beta_{u,c}. Changing \sigma_w changes only \pi_u, so (115), applied to the vector (z_c\beta_{u,c})_c, gives (117).

We now record the insertion estimates used below. For a fixed colour c, set

M_c=\sum_{u\in U}(\pi_{u,c}-p_{u,c}),\qquad Y_c(\xi)=\prod_{u\in U}(1-s\pi_{u,c}(\xi)). \tag{120}

Conditional independence gives T_c=\mathbb E_\nu Y_c. Applying (115) in each disjoint set W_u and then (113) gives

\operatorname{Var}_\nu(\pi_{u,c})\le V_\pi,\qquad \operatorname{Var}_\nu(M_c)\le V_M. \tag{121}

For 0\le y\le B, set \mathfrak r(y):=-\log(1-y)-y. The bound 0\le\mathfrak r(y)\le y^2/[2(1-B)] gives

\zeta_c:=\sum_{u\in U} \bigl(\mathfrak r(sp_{u,c})-\mathfrak r(s\pi_{u,c})\bigr), \qquad \log\frac{Y_c}{Q_c}=-sM_c+\zeta_c, \qquad |\zeta_c|\le D_\Deg. \tag{122}

Indeed, each of the two remainder sums lies in [0,D_\Deg]. Since \mathbb E_\nu M_c=0 and |M_c|\le\Deg B, the exponential Taylor bound gives 1\le\mathbb E_\nu e^{-sM_c}\le 1+\tfrac12e^{\Deg B}V_M. It follows that

\left|\log\frac{T_c}{Q_c}\right|\le E_\Deg,\qquad T_c\ge e^{-\Deg B-D_\Deg}. \tag{123}

Finally,

\beta_{u,c}=s\left(\frac1{1-sp_{u,c}}-\frac1{1-s\pi_{u,c}}\right) +\frac{s}{1-s\pi_{u,c}}\left(1-\frac{Y_c}{T_c}\right). \tag{124}

To bound the variance, put

\Phi_c:=\exp\!\left(-s\sum_{u\in U}\pi_{u,c}\right) =\exp\!\left(-s\sum_{u\in U}p_{u,c}\right)e^{-sM_c}.

Then Y_c=\Phi_c\exp(-\sum_u\mathfrak r(s\pi_{u,c})), so 0\le Y_c\le\Phi_c\le1 and |Y_c-\Phi_c|\le D_\Deg. As a function of M_c on its range, \Phi_c is s-Lipschitz. Thus (121) gives \operatorname{Var}_\nu(\Phi_c)\le s^2\operatorname{Var}_\nu(M_c)\le V_M. Minkowski therefore gives \sqrt{\operatorname{Var}_\nu(Y_c)}\le\sqrt{V_M}+D_\Deg. Together with 1/(1-s\pi_{u,c})\le a_B, we obtain

\|\beta_{u,c}\|_{L^2(\nu)}\le a_B^2\sqrt{V_\pi} +a_Be^{\Deg B+D_\Deg}(\sqrt{V_M}+D_\Deg)\le b_\Deg. \tag{125}

Since the coordinate blocks W_u are disjoint (we do not assume that the corresponding spins are mutually independent) and \sum_u|W_u|\le\Deg^2, (113) now gives

\operatorname{Var}_\nu\left(\sum_cz_cG_c\right)\le V_Mb_\Deg^2\|z\|_2^2.

This is (118), and the weighted covariance estimate (119) follows by conjugation.

We now use these estimates to bound the response to a root-colour change uniformly over residual instances.

Theorem 9.4 (Unrestricted girth-five coupling independence). For every fixed 0<\delta\le1 there is a threshold \Deg_5(\delta)\ge\Deg_0(\delta) such that, whenever \Deg\ge\Deg_5(\delta) and q\ge(1+\delta)\Deg, every graph G\in\Gdeg and pinning \tau with \operatorname{girth}(G^\tau)\ge5 satisfies

\WHam\!\left( \mupin{G}{\tau^{r=c}}{x}, \mupin{G}{\tau^{r=d}}{x} \right)\le C_5(q,\Deg,\delta)<\infty

for every r\in V^\tau, all c,d\in\colours, and every x\in[0,1]. The same constant applies to all graphs and pinnings in this class, and both laws are on V^\tau\setminus\{r\}.

Proof. For the response estimates, let I=(H,\mathbf b) be a residual instance of girth at least five satisfying the degree budget, and fix \chi\ge1. Choose a positive weight vector \mathbf a=(a_w)_{w\in V(H)} with \chi^{-1}\le a_u/a_w\le\chi on every free edge. Let f_I=\sum_w f_w(\sigma_w), where f_w:\colours\to\mathbb R and |f_w(c)|\le a_w for every colour c. In a smaller residual instance J, f_J denotes the sum of the remaining source terms. All bounds below are uniform over further pinnings, deletions, and x\in(0,1). We first derive the exact response identity, then prove uniform weighted 2- and \infty-norm bounds by induction, and finally convert those bounds into a root-colour Hamming coupling.

Response recursion. For a free vertex v, put U=N_H(v), S=S_2^H(v), O=V(H)\setminus(\{v\}\cup U\cup S), and \nu=\mu_{I-v}. Use F_c,R_c,G_c from Lemma 9.3 for this instance. Put d=|U| and enumerate U as u_1,\ldots,u_d. Write

h_{I,v}(c)=\frac{\sqrt{p_{I,v}(c)}}{1-sp_{I,v}(c)} \left(\mathbb E_I[f_I\mid\sigma_v=c]-\mathbb E_I f_I\right). \tag{126}

For n\ge1, let U_n and V_n be the suprema of \|h_{I,v}\|_2/a_v and \|h_{I,v}\|_\infty/(\sqrt B a_v) over all such instances with at most n free vertices, all admissible weights and sources, all free roots, and all x\in(0,1). Set U_0=V_0=0. These suprema are finite at each fixed n: components not containing v cancel from the centred response, and weights in the root component differ from a_v by at most \chi^{n-1}. When analysing a particular I, write n=|V(H)|.

For a real parameter t, define the tilted law and its marginals by

d\mu_{J,t}:=\frac{e^{tf_J}}{\mathbb E_J[e^{tf_J}]}\,d\mu_J, \qquad p_{J,w}(c;t):=\mu_{J,t}(\sigma_w=c).

Thus p_{J,w}(c;0)=p_{J,w}(c). Set \nu_t:=\mu_{I-v,t}. Under this perturbation, the exact marginal identity is

p_{I,v}(c;t)\propto x^{b_v(c)}e^{tf_v(c)} \prod_{u\sim v}(1-sp_{I-v,u}(c;t))e^{e_{v,c}(t)},

where

e_{v,c}(t)=\log\mathbb E_{\nu_t}F_c -\sum_{u\sim v}\log(1-s\mathbb E_{\nu_t}X_{u,c}), \qquad e'_{v,c}(0)=\operatorname{Cov}_\nu(f_{I-v},R_c).

Set D_v=\operatorname{diag}(\sqrt{p_{I,v}}/(1-sp_{I,v})) and e'_v=(e'_{v,c}(0))_{c\in\colours}, with coordinatewise operations inside the diagonal. Write f:=f_{I-v} and f_A:=\sum_{w\in A}f_w(\sigma_w) for A\in\{U,S,O\}. Then f=f_U+f_S+f_O. Setting F_S=\mathbb E_\nu[f\mid\sigma_S], the disintegration gives the exact source decomposition

e'_{v,c}(0)= \underbrace{\mathbb E_\nu[\operatorname{Cov}_\nu(f_U,R_c\mid\sigma_S)]}_{A_c} +\underbrace{\operatorname{Cov}_\nu(F_S,G_c)}_{C_c}. \tag{127}

The local term satisfies

|A_c|\le 2\Deg B b_\Deg\chi a_v =\ell_\Deg\chi a_v, \tag{128}

using |f_u|\le a_u\le\chi a_v. To control the second term, reveal S one spin at a time. At one step, in the resulting smaller conditional instance J, let

g(c)=\mathbb E_J[f_J\mid\sigma_w=c]-\mathbb E_J f_J.

The conditional variance of this Doob increment is

\sum_c p_{J,w}(c)g(c)^2 =\sum_c(1-sp_{J,w}(c))^2h_{J,w}(c)^2 \le\|h_{J,w}\|_2^2 \le a_w^2U_{n-1}^2. \tag{129}

The Doob increments are orthogonal, so summing over w\in S gives

\operatorname{Var}_\nu(F_S) \le\sum_{w\in S}a_w^2U_{n-1}^2 \le\Deg^2\chi^4a_v^2U_{n-1}^2. \tag{130}

Differentiating the marginal identity at t=0 gives

h_{I,v}=\sum_{u\sim v}J_{v,u}h_{I-v,u} +D_v(I_q-\mathbf1p_{I,v}^{\mathsf T})(f_v+e'_v),\quad J_{v,u}=-sD_v(I_q-\mathbf1p_{I,v}^{\mathsf T}) \operatorname{diag}\sqrt{p_{I-v,u}}. \tag{131}

Set t_\delta=(1+\delta)^{-1} and \ell_B=-\log(1-B)/B. Here is the weighted AM–GM calculation used below. Put k_v=\sum_cb_v(c) and let C_0=\{c:b_v(c)=0\}, so that Q:=|C_0|\ge q-k_v\ge m+d. Write y_i(c)=s p_{I-v,u_i}(c)\in[0,B] and A_c=\prod_i(1-y_i(c)). Define the reference root marginal

\bar p(c):=\frac{x^{b_v(c)}A_c}{\sum_d x^{b_v(d)}A_d}.

The insertion quotient bound above gives

p_{I,v}(c)= \frac{\bar p(c)e^{e_{v,c}(0)}} {\sum_d\bar p(d)e^{e_{v,d}(0)}}.

Thus e^{-2E_\Deg}\le p_{I,v}(c)/\bar p(c)\le e^{2E_\Deg}. Since the factors x^{b_v(c)} are at most one, the normalizing denominator of \bar p is at least \sum_{c\in C_0}A_c. For each i, -\log(1-y_i(c))\le\ell_B y_i(c); hence AM–GM over C_0 gives

\sum_{c\in C_0}A_c \ge Q\left(\prod_{c\in C_0}A_c\right)^{1/Q} \ge Q\exp\!\left(-\frac{d\ell_B}{Q}\right).

For a fixed colour c and S_c=\sum_i y_i(c), ordinary AM–GM gives A_c\le(1-S_c/d)^d (the case d=0 is void), while S(1-S/d)^d\le (d/(d+1))^{d+1}=d^{d+1}/(d+1)^{d+1}\le e^{-1} for 0\le S\le d, with equality at S=d/(d+1). Therefore, with \theta=d/Q,

\bar p(c)S_c\le Q^{-1}e^{\theta\ell_B-1},\qquad d\max_c\bar p(c)S_c \le\theta e^{\theta\ell_B-1} \le t_\delta e^{t_\delta\ell_B-1},

because Q\ge m+d, m\ge\delta d, and \theta\le(1+\delta)^{-1}=t_\delta. Together with the insertion defect bound this yields

r_\Deg=e^{E_\Deg} \frac{\sqrt{t_\delta\exp(t_\delta\ell_B-1)}}{1-B},

which tends to e^{-\lambda_\delta}<1, where \lambda_\delta=\tfrac12(\log(1+\delta)+\delta/(1+\delta)). For completeness, write p=p_{I,v}, r_i=p_{I-v,u_i}, \mathbf z=\sqrt p, and \Lambda=\max_c p(c)\sum_i r_i(c). Then

J_i=-s\,\operatorname{diag}\!\left(\frac1{1-sp}\right) (I_q-\mathbf z\mathbf z^{\mathsf T})\operatorname{diag}\!\left(\sqrt{p\,r_i}\right),

so the projection identity and Cauchy–Schwarz give

\left\|\sum_iJ_ih_i\right\|_2 \le\frac{s\sqrt{d\Lambda}}{1-B}\max_i\|h_i\|_2.

The weighted AM–GM bound above and e^{-2E_\Deg}\le p(c)/\bar p(c)\le e^{2E_\Deg} turn this coefficient into r_\Deg: indeed, if \Lambda=\max_c p(c)\sum_i r_i(c), then

s^2d\Lambda\le e^{2E_\Deg} \bigl(d\max_c\bar p(c)\,s\sum_i r_i(c)\bigr) \le e^{2E_\Deg}t_\delta e^{t_\delta\ell_B-1},

using s\le1. Taking the square root is why the insertion loss is e^{E_\Deg} rather than e^{2E_\Deg}. For the infinity norm, write coordinatewise

\left(\sum_iJ_ih_i\right)_c =-\frac{s\sqrt{p(c)}}{1-sp(c)} \left[\sum_i\sqrt{r_i(c)}h_i(c) -\sum_d p(d)\sum_i\sqrt{r_i(d)}h_i(d)\right].

The first (diagonal) term is bounded by s\sqrt{d\Lambda}(1-B)^{-1}\max_i\|h_i\|_\infty. For the second term, Cauchy–Schwarz in the joint indices (i,d) gives

\sum_{i,d}p(d)\sqrt{r_i(d)}|h_i(d)| \le \sqrt{d\Lambda}\max_i\|h_i\|_2, \qquad \sum_{i,d}p(d)^2r_i(d)\le\Lambda,

and multiplying by \sqrt{p(c)}\le\sqrt B yields

\sqrt{p(c)}\sum_d p(d)\sum_i\sqrt{r_i(d)}|h_i(d)| \le\sqrt B\,\sqrt{d\Lambda}\max_i\|h_i\|_2.

Multiplying by s/(1-B) and applying the preceding coefficient bound gives the analogous infinity-norm estimate. These Jacobian blocks consequently satisfy

\left\|\sum_iJ_{v,u_i}h_i\right\|_2 \le r_\Deg\max_i\|h_i\|_2,\qquad \left\|\sum_iJ_{v,u_i}h_i\right\|_\infty \le r_\Deg\max_i\|h_i\|_\infty +r_\Deg\sqrt B\max_i\|h_i\|_2. \tag{132}

When d=0, the empty block sums and their norms are zero; maxima of nonnegative quantities over an empty neighbour set are also taken to be zero. The source term is controlled by the elementary bounds

\|D_v(I_q-\mathbf1p_{I,v}^{\mathsf T})g\|_2 \le a_B\sqrt{\operatorname{Var}_{p_{I,v}}(g)}, \qquad \|D_v(I_q-\mathbf1p_{I,v}^{\mathsf T})g\|_\infty \le 2a_B\sqrt B\|g\|_\infty. \tag{133}

Contractive induction. We now bound the previously defined U_n,V_n by induction on n. The full source f_U+f_S+f_O is retained, including the terms outside the second layer. Revealing the spins in S one at a time gives Doob increments which are exactly scores in successively pinned instances satisfying the degree budget; hence the induction only uses smaller instances. Lemma 9.3, the two source bounds, and (132) give

U_n\le (r_\Deg\chi+a_B\widetilde\epsilon_\Deg\chi^2)U_{n-1} +a_B(1+\ell_\Deg\chi), \tag{134}

V_n\le r_\Deg\chi V_{n-1} +(r_\Deg\chi+2a_BK_\Deg\chi^2)U_{n-1} +2a_B(1+\ell_\Deg\chi). \tag{135}

Choose \chi=e^{\lambda_\delta/4}. For sufficiently large \Deg, A_V=r_\Deg\chi<1 and A_U=r_\Deg\chi+a_B\widetilde\epsilon_\Deg\chi^2<1. Thus

U^*=\frac{a_B(1+\ell_\Deg\chi)}{1-A_U},\qquad V^*=\frac{(A_V+2a_BK_\Deg\chi^2)U^* +2a_B(1+\ell_\Deg\chi)}{1-A_V} \tag{136}

are finite supersolutions, and U_n\le U^*, V_n\le V^* for all n.

From response bounds to coupling independence. Define M_n as the supremum, over the same instances, pinnings, weights, sources, free roots, and n-vertex size range used for U_n,V_n, of

\frac{\left|\mathbb E_I[f_I\mid\sigma_v=c] -\mathbb E_I[f_I\mid\sigma_v=d]\right|}{a_v}, \qquad c,d\in\colours. \tag{137}

To recover this unweighted root-colour response, take differences of two logarithmic coordinates in (131) before dividing by a root marginal. This gives

M_n\le2\bigl(1+\ell_\Deg\chi+K_\Deg\chi^2U_{n-1}\bigr) +2\Deg B\chi V_{n-1},

so

M^*=2\bigl(1+\ell_\Deg\chi+K_\Deg\chi^2U^*\bigr) +2\Deg B\chi V^*<\infty. \tag{138}

Choosing source signs at the fixed real base point and applying (138) yields, for every admissible \mathbf a and every pair of root colours,

\sum_{w\ne v}a_w\, \|\mu_{I,w}^{v=c}-\mu_{I,w}^{v=d}\|_{\rm TV} \le \frac{M^*}{2}a_v. \tag{139}

It remains only to perform the standard coupling conversion. Work in the connected component of the root, since other components have identical laws under both root pinnings. For a current residual graph H, first take a_w=\chi^{\operatorname{dist}_H(v,w)}. For the fixed-ambient condition in [CLMM23, Lemma 5.13], apply (139) after every further pinning, using the restriction of a_w=\chi^{\operatorname{dist}_{H_0}(v,w)} from the original free graph H_0. These are separate applications; no comparison of the two distance functions is used. Choose R so that M^*\chi^{-R}/2\le(8R\log\Deg)^{-1}. Restricting (139) to the fixed-ambient sphere and applying [CLMM23, Lemma 5.13] gives a graph-size-independent Hamming coupling. The endpoint x=0 follows by finite-state continuity for the normalized child laws (proper list colourings exist because q\ge\Deg+1); at x=1 the root-excluded laws coincide directly.

9.2Spectral gap used in the CI proof

This subsection proves (113) on every residual instance satisfying (110) and having girth at least five. We use \Deg_0(\delta) and \gamma_\delta from (112), under the same hypothesis q\ge(1+\delta)\Deg. Throughout, P_v is conditional expectation given all spins except \sigma_v, and Q_v:=I-P_v. Heat-bath updates occur at rate one per free vertex. All operator inequalities are on the supported L^2 space of the current Gibbs law: A\succeq B means that A-B is positive semidefinite. We write \|f\|_\mu^2:=\mathbb E_\mu|f|^2 and similarly for \rho. Unsubscripted function norms are in L^2(\mu), and unsubscripted operator norms are the induced Hilbert-space norms. Finite colour matrices instead carry the subscript 2\to2. The identity I acts on the space in question, and \{A,B\}:=AB+BA denotes the anticommutator.

Lemma 9.5 (Star bounds and singleton complement). Fix 0<\delta\leq1, \Deg\geq\Deg_0(\delta), q\ge(1+\delta)\Deg, and x\in[0,1], and put s=1-x. Consider a supported conditional star from a residual instance satisfying (110) at every free vertex. Its centre has d free leaves and k fixed neighbours, with d+k\leq\Deg. Write

\mu(c,\sigma)=\frac{a_c}{Z}\prod_{i=1}^{d} \bigl[p_i(\sigma_i)(1-s\mathbf1_{\{\sigma_i=c\}})\bigr], \qquad a_c=x^{b(c)},\quad \sum_cb(c)=k,

where b(c) counts fixed neighbours of colour c and each p_i is the cavity law obtained after deleting the centre edge. Here c\in\colours is the centre colour and \sigma=(\sigma_1,\ldots,\sigma_d) is the leaf configuration. The normalizing constant is Z=\sum_c a_c\prod_i(1-sp_i(c)). Let \nu be the centre marginal and \rho=\bigotimes_i p_i the product cavity law on the leaves; \mu_{\rm leaves} denotes the actual leaf marginal. Set

B_{\rm SG}=\frac{1}{\delta\Deg},\qquad \kappa=\frac{B_{\rm SG}^2}{(1-B_{\rm SG})^2},\qquad \omega_{\rm SG}=\frac{sB_{\rm SG}}{(1-B_{\rm SG})^2},\qquad c_\delta=\frac{\delta}{1+\delta}.

Then, uniformly over all supported stars (including x=0),

s p_i(c)\le B_{\rm SG},\quad s\nu(c)\le B_{\rm SG},\quad \mathcal R:=\frac{d\mu_{\rm leaves}}{d\rho}\ge c_\delta. \tag{140}

Let P be the centre heat-bath projection and Q=I-P, and let P_i and Q_i=I-P_i denote the heat-bath projection and its complement at leaf i. Decompose the mean-zero space into the conditional leaf Hoeffding sectors K_0\oplus K_1\oplus K_{\ge2}: K_0 consists of mean-zero functions of the centre, and K_1 is the orthogonal sum of the spaces of functions g_i(c,\sigma_i) with \mathbb E[g_i\mid c]=0, and K_{\ge2} is the sum of higher conditional Hoeffding sectors, involving at least two distinct conditionally centred leaf factors and allowing coefficients that depend on c. Write K_+:=K_1\oplus K_{\ge2}. For a closed subspace \mathcal S, \Pi_{\mathcal S} denotes orthogonal projection in L^2(\mu). Block subscripts indicate the target and source sectors; for example, P_{ab}:=\Pi_{K_a}P|_{K_b} for a,b\in\{0,+\}. Put

C=P_{+0}(I-P_{00})^{-1}P_{0+},\qquad H=I-P_{++}-C,

whenever r:=\|P_{00}\|<1, and let H_{11} be the compression of H to K_1. If \mathcal A is the subspace generated by leaf-additive residuals h_i(\sigma_i)-\mathbb E[h_i(\sigma_i)\mid c], and \mathcal B=K_1\ominus\mathcal A, then

r\le r_*:=\frac{d\kappa(1+\omega_{\rm SG})^{d-1}}{c_\delta},\qquad H_{11}|_{\mathcal B}\succeq(1-\eta)I, \quad \eta:=r_*+\varepsilon_1,

where

\varepsilon_1= \begin{cases} \dfrac{2(d-1)\kappa(1+\omega_{\rm SG})^{d-2}} {c_\delta(1-B_{\rm SG})},&d\ge2,\\[3pt] 0,&d\le1. \end{cases} \tag{141}

Moreover, for d\ge1, put \theta_0=(1+\delta/2)^{-1}. Then

\Pi_{\mathcal A}C\Pi_{\mathcal A}\preceq \frac{\theta_0}{d}\Pi_{\mathcal A}. \tag{142}

Proof. If d=0, then \mathcal A=\{0\} and there is no additive sector to control. All estimates below containing 1/d, including (142), are used only when d\ge1. At a free vertex with k fixed and d free neighbours, let Z_{\rm loc} be the sum of its q conditional colour weights after the other spins are fixed. The degree budget gives Z_{\rm loc}\ge q-s(k+d)\ge\delta\Deg. Hence every one-site marginal satisfies sp_i(c),s\nu(c)\le B_{\rm SG}. If A_0=\sum_ca_c, then A_0\ge q-sk\ge s(d+\delta\Deg) and

\mathcal R(\sigma)=\frac{\sum_ca_c\prod_i(1-s\mathbf1_{\{\sigma_i=c\}})} {\sum_ca_c\prod_i(1-sp_i(c))} \ge \frac{A_0-sd}{A_0} \ge \frac{\delta\Deg}{d+\delta\Deg}\ge c_\delta .

At s=0 this is interpreted by continuity. At x=0, centre-colour coordinates and sums weighted by \nu may be restricted to \mathcal C_*=\{c:\nu(c)>0\}; zero-\nu terms vanish. Each leaf expectation and sum retains the full support of its own cavity law p_i.

For the complement estimate define

l_i^c=\frac{1-s\mathbf1_{\{\sigma_i=c\}}}{1-sp_i(c)}, \qquad \xi_i^c=l_i^c-1, \qquad \mathcal R=\sum_c\nu(c)\prod_i l_i^c .

The one-leaf Gram matrix is

\Psi_i(c,c')=\mathbb E_{p_i}[\xi_i^c\xi_i^{c'}] =\frac{s^2(\mathbf1_{c=c'}p_i(c)-p_i(c)p_i(c'))} {(1-sp_i(c))(1-sp_i(c'))}.

It is positive semidefinite and

\|\operatorname{diag}(\sqrt\nu)\Psi_i\operatorname{diag}(\sqrt\nu)\|_{2\to2} \le\kappa,\qquad \max_c\Psi_i(c,c)\le \omega_{\rm SG}. \tag{143}

The Schur product norm bound for positive semidefinite matrices therefore implies, for every nonempty J\subseteq[d], the following bound, where \circ denotes entrywise (Schur) multiplication:

\left\|\operatorname{diag}(\sqrt\nu) \Big(\mathop{\circ}_{j\in J}\Psi_j\Big) \operatorname{diag}(\sqrt\nu)\right\|_{2\to2} \le\kappa \omega_{\rm SG}^{|J|-1}. \tag{144}

If g=\sum_i g_i\in K_1\ominus\mathcal A, then orthogonality to every h_i(\sigma_i)-\mathbb E[h_i\mid c], together with \mathbb E[g_i\mid c]=0, gives \mathbb E_\mu[g_i\mid\sigma_i]=0. Bayes’ formula therefore gives \sum_c\nu(c)g_i(c,\sigma_i)l_i^c=0; this is the vanishing constant term in the following L^2(\rho)-orthogonal expansion (and \mathbb E_{p_i}[g_i(c,\cdot)l_i^c]=0 ensures that the displayed terms indexed by distinct I are in distinct product Hoeffding sectors):

(Pg)\mathcal R=\sum_{\substack{I\subseteq[d]\\|I|\ge2}} \sum_{i\in I}\sum_c \nu(c)g_i(c,\sigma_i)l_i^c \prod_{j\in I\setminus\{i\}}\xi_j^c . \tag{145}

For fixed I,i, (144), followed by (l_i^c)^2\le l_i^c/(1-B_{\rm SG}), yields

\left\|\sum_c\nu(c)g_i(c,\sigma_i)l_i^c \prod_{j\in I\setminus\{i\}}\xi_j^c\right\|_\rho^2 \le \frac{\kappa \omega_{\rm SG}^{|I|-2}}{1-B_{\rm SG}}\|g_i\|_\mu^2. \tag{146}

Summing the orthogonal Hoeffding components and using \|\sum_{i\in I}u_i\|^2\le |I|\sum_i\|u_i\|^2 gives

\|(Pg)\mathcal R\|_\rho^2\le \frac{2(d-1)\kappa(1+\omega_{\rm SG})^{d-2}}{1-B_{\rm SG}}\|g\|_\mu^2.

Since \|Pg\|_\mu^2=\mathbb E_\rho[((Pg)\mathcal R)^2/\mathcal R], (140) gives \|Pg\|_\mu^2\le\varepsilon_1\|g\|_\mu^2 with \varepsilon_1 as in (141). Together with C\preceq rI below, this yields H_{11}|_{\mathcal B}\succeq(1-r_*-\varepsilon_1)I.

For a mean-zero function h of the centre alone, the expansion of (Ph)\mathcal R starts in degree one; (144) and the same calculation give \|Ph\|^2\le r_*\|h\|^2, which is the bound on r. The projection identities P_{0+}P_{+0}=P_{00}-P_{00}^2 and P_{++}P_{+0}=P_{+0}(I-P_{00}) imply H^2=H and 0\preceq C\preceq rI.

It remains to prove (142). For a leaf-additive function h=\sum_i h_i, write \bar h=\mathbb E[h\mid c] and a=h-\bar h. Conditional independence gives a\in\mathcal A and \|a\|^2=\sum_i\mathbb E\operatorname{Var}(h_i\mid c). The exact block relations for Ph=h imply

(I-P_{00})\bar h=P_{0+}a,\qquad \langle a,Ca\rangle=\|Q\bar h\|^2. \tag{147}

After subtracting constants from each h_i, normalize \mathbb E_{p_i}h_i=0. Then \bar h_i(c):=\mathbb E[h_i(\sigma_i)\mid c]=-sp_i(c)h_i(c)/(1-sp_i(c)) and a direct channel computation gives

\mathcal D_i:=\mathbb E\operatorname{Var}(h_i\mid c) =\sum_cp_i(c)h_i(c)^2 \left[A_i-\frac{s\nu(c)}{(1-sp_i(c))^2}\right],\quad A_i=\sum_c\frac{\nu(c)}{1-sp_i(c)}.

Thus \mathcal D_i\ge\kappa_{B_{\rm SG}}\sum_cp_i(c)h_i(c)^2, where \kappa_{B_{\rm SG}}=1-B_{\rm SG}/(1-B_{\rm SG})^2\ge1-2B_{\rm SG}. Cauchy–Schwarz in the colour coordinate gives

\|Q\bar h\|^2\le \frac{s^2}{(1-B_{\rm SG})^2} \max_c\left[\nu(c)\sum_i p_i(c)\right] \sum_{i,c}p_i(c)h_i(c)^2. \tag{148}

Let u=sd/A_0. Since A_0\ge s(d+\delta\Deg), u\le(1+\delta)^{-1}. Weighted AM–GM gives

Z\ge A_0\exp[-u/(1-B_{\rm SG})],\qquad a_c\sum_i sp_i(c)\prod_i(1-sp_i(c))\le e^{-1}.

Consequently

\frac{ds^2}{(1-B_{\rm SG})^2}\max_c\left[\nu(c)\sum_i p_i(c)\right] \le \frac{u}{(1-B_{\rm SG})^2}e^{u/(1-B_{\rm SG})-1} \le \frac{1}{1+3\delta/4}. \tag{149}

(The last elementary inequality follows from B_{\rm SG}\le\delta/[8(1+\delta)].) Combining (148)–(149) yields

d\|Q\bar h\|^2\le \frac{1}{(1+3\delta/4)\kappa_{B_{\rm SG}}}\|a\|^2 \le \frac{1}{1+\delta/2}\|a\|^2,

which, by (147), is exactly (142). All statements use only supported coordinates, so the endpoint x=0 is included.

Lemma 9.6 (Unequal-incidence star inequality). Under the hypotheses of Lemma 9.5, put

\theta=\frac{1+\delta/4}{1+\delta/2}<1.

If \Deg\ge\Deg_0(\delta), then for every directed incidence choice 0<\beta_i<2 and every supported conditional star,

T_\beta:=Q+\tfrac12\{Q,W\}+D \succeq \frac{1}{2}Q-\frac{\theta}{2d}\sum_i\beta_i^2Q_i, \quad W=\sum_i\beta_iQ_i,\quad D=N^2-N,\ N=\sum_iQ_i, \tag{150}

where \theta is as above. When d=0, the sum on the right is empty and the assertion means simply T_\beta=Q\succeq\frac12Q; hence the displayed inequality is understood for d\ge1.

Proof. We give the Schur-complement argument, including the constants. On K_+, put K=\tfrac12H+\tfrac12(HW+WH)+D. Let \mathcal A and \mathcal B be as above. The assertion H\mathcal A=0 uses the special form of \mathcal A, not merely the fact that H is a projection. If a=h-\mathbb E[h\mid c]\in\mathcal A with h=\sum_i h_i(\sigma_i), then Ph=h because h is independent of the centre spin. Remove the global constant from h (which does not change a), and write h=h_0+a with h_0=\mathbb E[h\mid c]\in K_0, the K_0 and K_+ blocks of Qh=0 are

(I-P_{00})h_0=P_{0+}a, \qquad (I-P_{++})a=P_{+0}h_0.

Consequently Ca=P_{+0}(I-P_{00})^{-1}P_{0+}a=P_{+0}h_0, and hence Ha=(I-P_{++}-C)a=0. Moreover, \mathcal A=\bigoplus_i\mathcal A_i with \mathcal A_i=\{h_i(\sigma_i)-\mathbb E[h_i\mid c]\}, so Q_i is the identity on \mathcal A_i and vanishes on \mathcal A_j for j\ne i. Thus W is diagonal on \mathcal A; since it is self-adjoint, it also preserves \mathcal A^\perp=\mathcal B\oplus K_{\ge2}. On \mathcal B, writing H_{11}=I-E, 0\preceq E\preceq\eta I, one has

K_{11}\succeq(1/2-5\eta/2)I. \tag{151}

For f\in K_{\ge2}, completing the square gives

\frac{1}{2}\langle f,Hf\rangle+\Re\langle Hf,Wf\rangle \ge-\frac{1}{6}\|(W-I)f\|^2.

Indeed, with u=Hf and b=(W-I)f, the projection property H^*=H^2=H gives

\frac12\langle f,Hf\rangle+\Re\langle Hf,Wf\rangle =\frac32\|u\|^2+\Re\langle u,b\rangle =\frac32\left\|u+\frac13b\right\|^2-\frac16\|b\|^2,

which proves the displayed bound. On a conditional Hoeffding sector of degree n\ge2, each Q_i is either zero or the identity, so 0\le W=\sum_i\beta_iQ_i\le2nI. Therefore (W-I)^2\preceq(2n-1)^2I\preceq\frac92n(n-1)I, since the scalar difference is \frac92n(n-1)-(2n-1)^2=\frac12(n-2)(n+1)\ge0 for n\ge2. Since W and D preserve these orthogonal sectors, this proves (W-I)^2\preceq\frac92D on all of K_{\ge2}. Applying the completed-square estimate to an arbitrary f\in K_{\ge2} therefore gives

\langle f,Kf\rangle \ge \langle f,Df\rangle-\frac16\|(W-I)f\|^2 \ge\frac14\langle f,Df\rangle.

Thus K_{\ge2,\ge2}\succeq D/4, including all cross-sector terms of H. The projection identity H_{1,\ge2}H_{\ge2,1}=H_{11}-H_{11}^2 gives \|H_{1,\ge2}\|\le\sqrt\eta. Since D\ge2I on the higher sectors,

\|K_{1,\ge2}D^{-1/2}\| \le \frac{1}{2}(3/\sqrt2+2\sqrt2)\sqrt\eta =\frac{7}{2\sqrt2}\sqrt\eta .

To record the numerical margin, set X=K_{1,\ge2}D^{-1/2}. Since \|X\|^2\le(49/8)\eta and the higher block is at least D/4, retaining D/8 leaves a Schur-complement loss at most 8\|X\|^2\le49\eta. The singleton block left after this elimination is therefore bounded below by

\left(\tfrac12-\tfrac52\eta\right)-\tfrac14-49\eta =\tfrac14-\tfrac{103}{2}\eta\ge0 \qquad(\eta\le5/2048).

Hence

K\succeq \frac{1}{4}\Pi_{\mathcal B}+\frac{1}{8}D. \tag{152}

On the other hand, for f\in K_+ write f=a+y, where a\in\mathcal A and y\in K_+\ominus\mathcal A. Positivity of C and Young’s inequality imply

\langle Wf,CWf\rangle \le(1+\epsilon)\langle Wa,CWa\rangle +(1+\epsilon^{-1})r\|Wy\|^2. \tag{153}

Because W^2=\sum_i\beta_i^2Q_i on \mathcal A, (142) bounds \langle Wa,CWa\rangle by \theta_0\langle a,W^2a\rangle/d. Furthermore \|Wy\|^2\le4\|y_1\|^2+8\langle y,Dy\rangle, where y_1:=\Pi_{\mathcal B}y is the singleton component of y. Take \epsilon=\delta/4. The threshold gives

r\le R_\delta:=\frac{2(1+\delta)e^{2/\delta}}{\delta^3\Deg} \le\frac{\delta}{2048},\qquad \eta\le5/2048,

so (1+\epsilon^{-1})r\le1/32. We now verify the claimed combination of (152) and (153). To make the Schur cancellation explicit, set E_\beta=(\theta/d)\sum_i\beta_i^2Q_i and consider A:=T_\beta-Q/2+E_\beta/2 on K_0\oplus K_+. Its blocks are

\begin{aligned} A_{00}&=\tfrac12(I-P_{00}), &A_{0+}&=-\tfrac12P_{0+}(I+W),\\ A_{++}&=\tfrac12(I-P_{++})+W-\tfrac12\{P_{++},W\}+D+\tfrac12E_\beta . \end{aligned}

Since A_{00}^{-1}=2(I-P_{00})^{-1}, eliminating K_0 subtracts \tfrac12(I+W)C(I+W). Using H=I-P_{++}-C and expanding the anticommutator, the resulting block is

\tfrac12H+\tfrac12\{H,W\}+D-\tfrac12WCW+\tfrac12E_\beta =K-\tfrac12WCW+\tfrac12E_\beta .

K-\tfrac12WCW+\frac{\theta}{2d}\sum_i\beta_i^2Q_i\succeq0. \tag{154}

Eliminating the degree-zero block (whose Schur complement is -\tfrac12WCW) proves (150). This step is valid because the correction vanishes on K_0.

Theorem 9.7 (Uniform spectral gap under the degree budget). Fix 0<\delta\le1, \Deg\ge\Deg_0(\delta) and q\ge(1+\delta)\Deg. Every finite Potts instance on a simple graph with \deg_H(v)+k_H(v)\le\Deg at each free vertex, after any normalized pinning whose free residual graph has girth at least five, and for every x\in[0,1], has the nonnegative rate-one Glauber Laplacian \mathcal L:=\sum_v(I-P_v) satisfying

\mathcal L^2\succeq\gamma_\delta \mathcal L, \qquad \gamma_\delta=\frac{\delta}{4(2+\delta)}. \tag{155}

Proof. For each free vertex v let d_v be its current free degree and choose, on an edge vu,

\beta_{vu}=\frac{2d_v}{d_v+d_u},\qquad W_v:=\sum_{u\sim v}\beta_{vu}Q_u,\qquad N_v:=\sum_{u\sim v}Q_u,\qquad T_v:=Q_v+\tfrac12\{Q_v,W_v\}+N_v^2-N_v.

Girth at least five implies that every distance-two pair has a unique common neighbour and that adjacent vertices have no common neighbour. Therefore

\mathcal L^2=\sum_vT_v+2\sum_{\{u,w\}:\,\operatorname{dist}_H(u,w)\ge3}Q_uQ_w. \tag{156}

The last sum is positive semidefinite because nonadjacent heat-bath projections commute. For an edge vu, both endpoint degrees are positive, and

\frac{\beta_{vu}^2}{d_v}=\frac{1}{d_u}\bigl(1-(\beta_{vu}-1)^2\bigr), \qquad \sum_{v\sim u}\frac{\beta_{vu}^2}{d_v}\le1. \tag{157}

For an isolated vertex u, the neighbour sum is empty. Applying (150) in every conditional-star fibre and summing with (157) shows

\mathcal L^2\succeq \frac{1-\theta}{2}\mathcal L =\frac{\delta}{4(2+\delta)}\mathcal L.

At x>0 the supported chain is irreducible. At x=0, remove from the colour list of a free vertex v the colours used by its k_v fixed neighbours, and denote the resulting list by L_v and its size by \ell_v. Since at most k_v colours are removed,

\ell_v-d_v\ \ge\ q-k_v-d_v \ \ge\ q-\Deg \ \ge\ \delta\Deg\ \ge\ 2,

where the last inequality is part of the choice of \Deg_0(\delta). Thus \ell_v\ge d_v+2 for every free vertex. For completeness, connectivity follows by induction on the number of free vertices. Given two proper list-colourings \alpha,\beta, choose a vertex v and put c=\beta(v). For every neighbour u of v with current colour \alpha(u)=c, recolour u (one at a time) to a colour in L_u different from c and from all colours currently used by the neighbours of u; at most d_u+1 colours are forbidden and \ell_u\ge d_u+2. Now recolour v to c. Keep v fixed at c and apply the induction hypothesis to H-v with the reduced lists L'_u=L_u\setminus\{c\} for neighbours of v and L'_u=L_u otherwise. These lists satisfy |L'_u|\ge\deg_{H-v}(u)+2, and the current and target restrictions are proper list-colourings. The base case has one vertex. Thus the proper-list-colouring support is connected, and (155) is the ordinary spectral-gap bound at the endpoint as well.

References

[Bar16]Alexander Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer, 2016.
[BBR25]Ferenc Bencs, Khallil Berrekkal, and Guus Regts. Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees. Electronic Journal of Probability, 30:Paper No. 65, 1–25, 2025.
[BCC+22]Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda. On mixing of Markov chains: Coupling, spectral independence, and entropy factorization. Electronic Journal of Probability, 27:Paper No. 142, 1–42, 2022. arXiv:2103.07459v1.
[CDM+19]Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. Improved bounds for randomly sampling colorings via linear programming. In Proceedings of SODA 2019, pages 2216–2234, 2019. Full version: arXiv:1810.12980v1; theorem numbering refers to this version.
[CFG+25]Xiaoyu Chen, Weiming Feng, Heng Guo, Xinyuan Zhang, and Zongrui Zou. Deterministic counting from coupling independence. In Proceedings of FOCS 2025, pages 667–683, 2025. Full version: arXiv:2410.23225v2; theorem numbering refers to this version.
[CL26]Xiaoyu Chen and Kuikui Liu. A spectral local-to-global principle for spin systems on graphs with girth at least five, 2026. arXiv:2608.25491.
[CLMM23]Zongchen Chen, Kuikui Liu, Nitya Mani, and Ankur Moitra. Strong spatial mixing for colorings on trees and its algorithmic applications. In Proceedings of FOCS 2023, pages 810–845, 2023. Full version: arXiv:2304.01954v3; theorem numbering refers to this version; journal version: J. ACM, 2026, doi:10.1145/3837755.
[CV25]Charlie Carlson and Eric Vigoda. Flip dynamics for sampling colorings: Improving (11/6-\epsilon) using a simple metric. In Proceedings of SODA 2025, pages 2194–2212, 2025. Full version: arXiv:2407.04870v2.
[CWZZ25]Zejia Chen, Yulin Wang, Chihao Zhang, and Zihan Zhang. Decay of correlation for edge colorings when q>3\Delta. In Proceedings of ICALP 2025, volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:18, 2025. Full version: arXiv:2502.06586v2; theorem numbering refers to this version.
[Ise93]Arieh Iserles. On the generalized pantograph functional-differential equation. European Journal of Applied Mathematics, 4(1):1–38, 1993.
[MFB72]Grainger R. Morris, Alan Feldstein, and Ernie W. Bowen. The Phragmén–Lindelöf principle and a class of functional differential equations. In Leonard Weiss, editor, Ordinary Differential Equations: 1971 NRL–MRC Conference, pages 513–540. Academic Press, 1972.
[PR17]Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal on Computing, 46(6):1893–1919, 2017.
[Shi26]Ke Shi. Coupling independence implies zero-freeness: Lean formalization. Source code and verification records, commit c388cfa, https://github.com/KeShih/coupling-independence-implies-zero-freeness/tree/c388cfa, 2026.
[SS26]Shuai Shao and Ke Shi. Coupling independence implies zero-freeness, 2026. Preprint.
[WZ18]Liuquan Wang and Cheng Zhang. Zeros of the deformed exponential function. Advances in Mathematics, 332:311–348, 2018. arXiv:1709.04357.