Proof. The claims about the total variation distance are shown in [Reference Helmuth, Jenssen and Perkins21, Theorem1, Items (2), (3), (8)]. Equation (2) shows a bit of slack in the definitions of $\Omega ^{\mathrm{dis}}$ and $\Omega ^{{\mathrm{ord}}}$ that will be useful later; it follows essentially from the same theorem, we defer the details to Lemma24.

Proof of Theorem 1. Follows immediately by Theorems11-13, since by Lemma3 we have that $\left \| \pi _G-\pi _G^{\mathrm{ord}}\right \|_{\mathrm{TV}}=\mathrm{e}^{-\Omega (n)}$ when $\beta \gt \beta _c$ and $\left \| \pi _G-\pi _G^{\mathrm{dis}}\right \|_{\mathrm{TV}}=\mathrm{e}^{-\Omega (n)}$ .

Proof of Theorem 11. The argument resembles that of [Reference Gheissari and Sinclair15], a bit of care is required to combine the pieces. Consider $G=(V,E)\sim{\mathcal{G}}_{n,\Delta }$ with $n=|V|$ and $m=|E|$ . Let $q$ be sufficiently large so that both Lemma3 and Theorem5 apply; assume also that Lemma7 applies so that $G$ is locally $K$ -treelike. By Lemma3, for every $\beta \geq \beta _c$ , $\pi _G^{\mathrm{ord}}\big (|{\mathrm{In}}({\mathcal{F}})|\leq (1-\zeta )|E|\big )=\mathrm{e}^{-\Omega (n)}$ .

From now on consider arbitrary $\beta \geq \beta _c$ and set $\beta _0\;:\!=\;\log (q^{1.9/\Delta }+1)$ . Since $\beta _c=(1+o_q(1))\tfrac{2\log q}{\Delta }$ , we have that $\beta \geq \beta _0$ for all sufficiently large $q$ . Moreover, by Theorem5, $G$ has WSM within the ordered phase at radius $r$ for some $r\leq \tfrac{M}{\beta }\log n$ , where $M=M(\Delta )\gt 0$ is a constant independent of $\beta$ . Note that by taking $q$ large, we can ensure that $\beta _0$ and hence $\beta$ are at least $3M\log (\Delta -1)$ so that $r\leq \tfrac{1}{3}\log _{\Delta -1}n$ (and hence the radius- $r$ neighbourhood of an arbitrary vertex in $G$ is locally $K$ -treelike).

We will consider the RC dynamics $(X_t)_{t\geq 0}$ with $X_0$ being the all-in configuration on the edges. We will also consider the ‘ordered’ RC dynamics $\hat{X}_t$ with $\hat{X}_0\sim \pi ^{\mathrm{ord}}_G$ where we reject moves that lead to configurations outside of $\Omega ^{{\mathrm{ord}}}$ ; since $\hat{X}_0$ is stationary note that $\hat{X}_t\sim \pi ^{\mathrm{ord}}_G$ for all $t\geq 0$ . We will show how to couple these two dynamics in $O(n^C)$ steps. The theorem will follow by showing that ${\mathrm{dist}}_{\mathrm{TV}}(X_T,\hat{X}_T)\leq 1/5$ , where $T=O(n^{2+\log W})$ with $W=\Delta ^{2M/\beta _0} \mathrm{e}^{M \Delta (\Delta +1)}$ being independent of $\beta$ .

Consider the dynamics $(X_t)_{t\geq 0}$ and $(\hat{X}_t)_{t\geq 0}$ . For $t\geq 0$ , let $\mathcal{E}_t$ be the event that ${\mathrm{In}}(\hat{X}_t)\geq (1-\zeta )|E|$ and let $\mathcal{E}_{\lt t}\;:\!=\;\bigcap _{t'=0,\ldots, t-1} \mathcal{E}_{t'}$ . From Lemma3 we have that $\pi ^{{\mathrm{ord}}}_G(\mathcal{E}_t)\geq 1-\mathrm{e}^{-\Omega (n)}$ and hence by a union bound $\pi ^{{\mathrm{ord}}}_G(\mathcal{E}_{\lt t})\geq 1-t\mathrm{e}^{-\Omega (n)}$ as well.

We couple the evolution of $X_t$ and $\hat{X}_t$ using the monotone coupling, that is, at every step of the two chains choose the same edge $e_t$ to update and use the same uniform number $U_t\in [0,1]$ to decide whether to include $e_t$ in each of $X_{t+1},\hat{X}_{t+1}$ . Using the monotonicity of the model for $q\geq 1$ (and in particular that $p\gt \hat{p}$ ), under the monotone coupling, for all $t\geq 0$ such that $\mathcal{E}_{\lt t}$ holds (and hence no reject move has happened in $\hat{X}_t$ so far), we have that $\hat{X}_t\leq X_t$ (i.e., ${\mathrm{In}}(\hat{X}_t)\subseteq{\mathrm{In}}(X_t)$ ). To complete the proof, it therefore suffices to show that

(3) \begin{equation} {\mathbb{P}}(X_T\neq \hat{X}_T)\leq 1/4. \end{equation}

Consider an arbitrary time $t\geq 0$ . By a union bound, we have that

(4) \begin{equation} {\mathbb{P}}\big (X_{t}\neq \hat{X}_t\big )\leq \sum _{e}{\mathbb{P}}\big (X_t(e)\neq \hat{X}_t(e)\big )\leq m{\mathbb{P}}\big (\overline{ \mathcal{E}_{\lt t}}\big )+\sum _{e}{\mathbb{P}}\big (X_t(e)\neq \hat{X}_t(e)\mid \mathcal{E}_{\lt t}\big ). \end{equation}

Fix an arbitrary edge $e$ incident to some vertex $v$ , and let $(X^v_t)$ be the wired RC dynamics on $G[B_r(v)]$ . We couple the evolution of $(X_t^v)$ with that of $(X_t)$ and $(\hat{X}_t)$ using the monotone coupling analogously to above, where in $X_t^v$ we ignore updates of edges outside the ball $G[B_r(v)]$ ). We have $X_t^v\geq X_t$ for all $t\geq 0$ , and hence, conditioned on $\mathcal{E}_{\lt t}$ , we have that $X^v_t\geq X_t\geq \hat{X}_t$ . It follows that

\begin{align*}{\mathbb{P}}\big (X_t(e)\neq \hat{X}_t(e)\mid \mathcal{E}_{\lt t}\big )&={\mathbb{P}}(X_t(e)=1\mid \mathcal{E}_{\lt t})-{\mathbb{P}}(\hat{X}_t(e)=1\mid \mathcal{E}_{\lt t})\\[5pt] &\leq |{\mathbb{P}}(X^v_t(e)=1\mid \mathcal{E}_{\lt t})-{\mathbb{P}}(\hat{X}_t(e)=1\mid \mathcal{E}_{\lt t})|. \end{align*}

For any two events $A,B$ , we have $|{\mathbb{P}}(A)-{\mathbb{P}}(A\mid B)|\leq 2{\mathbb{P}}(\overline{B})$ , so using this for $B=\mathcal{E}_{\lt t}$ and $A$ the events $\{X^v_t(e)=1\},\{\hat{X}_t(e)=1\}$ , the triangle inequality gives

\begin{align*}{\mathbb{P}}\big (X_t(e)\neq \hat{X}_t(e)\mid \mathcal{E}_{\lt t}\big ) \leq 4{\mathbb{P}}\big (\overline{ \mathcal{E}_{\lt t}}\big )+|{\mathbb{P}}(X^v_t(e)=1)-{\mathbb{P}}(\hat{X}_t(e)=1)| \end{align*}

Note that ${\mathbb{P}}(\hat{X}_t(e)=1)=\pi ^{{\mathrm{ord}}}_G(e\mapsto 1)$ , so another application of triangle inequality gives

(5) \begin{equation} \begin{aligned}{\mathbb{P}}\big (X_t(e)\neq \hat{X}_t(e)\mid \mathcal{E}_{\lt t}\big )\leq 4{\mathbb{P}}\big (\overline{ \mathcal{E}_{\lt t}}\big )+\big |{\mathbb{P}}(X^v_t(e)&=1)-\pi _{{\mathcal{B}}^+_r(v)}(e\mapsto 1)\big |\\[5pt] &+\big |\pi _{{\mathcal{B}}^+_r(v)}(e\mapsto 1)-\pi ^{{\mathrm{ord}}}_G(e\mapsto 1)\big |. \end{aligned} \end{equation}

Since $G$ has WSM within the ordered phase at radius $r$ , we have that

(6) \begin{equation} \big |\pi _{{\mathcal{B}}^+_r(v)}(e\mapsto 1)-\pi ^{{\mathrm{ord}}}_G(e\mapsto 1)\big |\leq 1/(100 m). \end{equation}

Moreover, let $T_v$ be the mixing time of the wired RC dynamics on $G[B_r(v)]$ and let $N_v=|E(B_r(v))|\leq \Delta ^{r+1}$ . Since $r\leq \tfrac{1}{3}\log _{\Delta -1} n$ , $G[B_r(v)]$ is $K$ -treelike, so from Lemma9, with $\hat{C}=O(1)$ denoting the constant there (and absorbing a couple of factors of $\Delta$ into it),

\begin{equation*}T_v\leq \hat {C} (N_v)^3 (q^4 \mathrm {e}^\beta )^{\Delta r}\leq \hat {C} N_v\Delta ^{2r}q^{4\Delta r}\mathrm {e}^{\beta \Delta r}= \hat {C} N_v \Big (\Delta ^{2M/\beta } q^{4\Delta M/\beta }\mathrm {e}^{M \Delta }\Big )^{\log n}\leq \hat {C} N_v W^{\log n},\end{equation*}

where in the last inequality we used that $\beta \gt \beta _0$ , $\beta _0\gt \tfrac{1}{\Delta }\log q$ and $W=\Delta ^{2M/\beta _0} \mathrm{e}^{M \Delta (\Delta +1)}$ . For $T=\Theta (n^{2+\log W})$ , we have $T\geq 40T_v \tfrac{m}{N_v}\log m$ , so by Chernoff bounds, with probability $1-\exp (-n^{\Omega (1)})$ , we have at least $10T_v \log m$ updates inside $B_r(v)$ among $t=1,\ldots, T$ . For integer $k\geq 1$ the distance from stationarity after $kT_v$ steps is at most $(1/4)^k$ , we obtain

(7) \begin{equation} \big |{\mathbb{P}}(X^v_T(e)=1)-\pi _{{\mathcal{B}}^+_r(v)}(e\mapsto 1)\big |\leq \exp (-n^{\Omega (1)})+ \mathrm{e}^{-4\log m}\leq 1/m^3. \end{equation}

Plugging (6) and (7) into (5) for $t=T$ , and then back into (4), we obtain using ${\mathbb{P}}(\overline{\mathcal{E}_{\lt T}})\leq T\mathrm{e}^{-\Omega (n)}$ that ${\mathbb{P}}(X_T\neq \hat{X}_T)\leq 5m T \mathrm{e}^{-\Omega (n)}+m/m^3+1/100\leq 1/5$ , as needed.

Proof. Apply Lemma17 with $E' = \mathrm{Out}({\mathcal{F}})$ and $\theta = \eta = \min (\delta /5,1/100)$ . Note $|\mathrm{Out}({\mathcal{F}})|\leq \eta |E|$ and $\phi _G(1/2)\geq 1/10$ . Thus the lemma say that $G[{\mathrm{In}}({\mathcal{F}})]$ has a component of size at least $\left (1-\frac{\delta / 5}{2\cdot 1/10}\right )|V| = (1 - \delta )|V| \gt |V|/2$ .

Proof. We prove the first bound, the second is similar. Choose $\zeta = 20 \Delta /\log (q_0)$ . Note that $\zeta \lt \eta$ , as desired. Let $\Omega ' = \{{\mathcal{F}} \in \Omega ^{\mathrm{ord}}\;:\; |{\mathrm{In}}({\mathcal{F}})|\leq (1-\zeta )|E|\}$ and let

\begin{equation*}Z' = \sum _{{\mathcal {F}} \in \Omega '} w_G({\mathcal {F}}) = \sum _{{\mathcal {F}}\in \Omega '} q^{c({\mathcal {F}})} (\mathrm {e}^\beta - 1)^{|{\mathrm {In}}({\mathcal {F}})|}.\end{equation*}

Let $z = \max \{q,(\mathrm{e}^{\beta }-1)^{\Delta /2}\}$ . Since $Z \geq z^n$ every ${\mathcal{F}}\in \Omega$ has

\begin{equation*}w_G({\mathcal {F}})/Z \leq z^{c({\mathcal {F}}) + 2|{\mathrm {In}}({\mathcal {F}})|/\Delta - n} = z^{n(c({\mathcal {F}})/n + |{\mathrm {In}}({\mathcal {F}})|/|E| - 1)} .\end{equation*}

Since $\zeta \lt \eta \lt 1/2$ , for any ${\mathcal{F}}\in \Omega '$ , $\zeta |E| \leq (1-\eta )|E| \leq |{\mathrm{In}}({\mathcal{F}})| \leq (1-\zeta )|E|$ . By Lemma16, w.h.p., $G\in \mathcal{G}_{\Delta, \delta }$ . By Lemma22, for $n\geq 360/(\zeta \delta )$ , we have $c({\mathcal{F}})/n + |{\mathrm{In}}({\mathcal{F}})|/|E| \leq 1-\zeta /40$ so $Z'/Z \leq 2^{n\Delta /2} z^{n(-\zeta /40)}$ , which gives $Z'/Z = \mathrm{e}^{-\Omega (n)}$ since $q \gt \mathrm{e}^{20 \Delta /\zeta }$ . To finish, we will show that $Z/Z^{\mathrm{ord}} = O(1)$ , so that $\frac{Z'}{Z^{\mathrm{ord}}} = \frac{Z'}{Z} \times \frac{Z}{Z^{\mathrm{ord}}} = \mathrm{e}^{-\Omega (n)} O(1) = \mathrm{e}^{-\Omega (n)}$ . If $\beta \gt \beta _c$ , item 3 of [Reference Helmuth, Jenssen and Perkins21, Theorem1] says that there are positive numbers $n_0$ and $\xi$ such that, for $n\geq n_0$ , $(1/n) \log ((Z-Z^{\mathrm{ord}})/Z) \leq -\xi$ . So for $n\geq n_0$ , $Z^{\mathrm{ord}}/Z \geq 1 - e^{-\xi n}$ , which is at least $1/2$ for $n\geq 1/\xi$ . If $\beta = \beta _c$ , then items 1 and 3 of [Reference Helmuth, Jenssen and Perkins21, Theorem 2] show that $Z^{\mathrm{ord}}/Z$ converges in distribution to a random variable $Q/(Q+1)$ where (say) $Q\geq q/2$ for $q\geq q_0$ . So for sufficiently large $q$ , $Z^{\mathrm{ord}}/Z = O(1)$ .

Proof. Let $q$ and $n$ be large enough so that Proposition 11 from [Reference Helmuth, Jenssen and Perkins21] applies, and so in particular [Reference Helmuth, Jenssen and Perkins21, Equation (13)] holds, and also that $s \gt 1$ and $q\geq e^{4\Delta (\frac{5}{2C}-1)}$ .

For a disordered configuration $\mathcal{F}$ , let $\Gamma ^{\mathrm{dis}}({\mathcal{F}})$ be the set of disordered polymers of $\mathcal{F}$ .

First we will bound, for a particular polymer $\gamma$ with $|E(\gamma )| \geq 1$ , ${\mathbb{P}}(\gamma \in \Gamma ^{\mathrm{dis}}(.))$ . Suppose ${\mathcal{F}}\in \Omega ^{\mathrm{dis}}$ has $\gamma \in \Gamma ^{\mathrm{dis}}({\mathcal{F}})$ . By Observation25, $w_G({\mathcal{F}}) = q^n \prod _{\gamma \in \Gamma ^{\mathrm{dis}}({\mathcal{F}})} w_\gamma ^{\mathrm{dis}}$ . Let ${\mathcal{F}}'$ be the (disordered) configuration defined by ${\mathrm{In}}({\mathcal{F}}') ={\mathrm{In}}({\mathcal{F}})\backslash E(\gamma )$ . Since $E(\gamma )\neq \emptyset$ , ${\mathcal{F}}\neq{\mathcal{F}}'$ . By construction, ${\mathcal{F}}'\in \Omega ^{\mathrm{dis}}$ . Since vertices in $\gamma$ are not incident to edges in ${\mathrm{In}}({\mathcal{F}}')$ , $\Gamma ^{\mathrm{dis}}({\mathcal{F}}') = (\Gamma ^{\mathrm{dis}}({\mathcal{F}})\setminus \{\gamma \})\cup _{v\in \gamma } \{v\}$ . A polymer $\gamma '$ consisting of a single vertex has weight $w_{\gamma '}^{\mathrm{dis}} = 1$ . Thus, $w_G({\mathcal{F}}') = w_G({\mathcal{F}})/w_\gamma ^{\mathrm{dis}}$ . Let $\Omega _\gamma$ be the set of all disordered configurations containing $\gamma$ as a polymer. Then $Z^{\mathrm{dis}} \geq \sum _{{\mathcal{F}}\in \Omega _\gamma } (w_G({\mathcal{F}}) + w_G({\mathcal{F}}')) = (1 + 1/w_\gamma ^{\mathrm{dis}})\sum _{{\mathcal{F}}\in \Omega _\gamma } w_G({\mathcal{F}})$ . Thus, the probability that ${\mathcal{F}}\sim \pi ^{\mathrm{dis}}$ contains the polymer $\gamma$ is at most $\frac{1}{1 + 1/w_\gamma ^{\mathrm{dis}}} \leq w_\gamma ^{\mathrm{dis}}$ .

Next, for $v\in V(G)$ let $p_v$ be the probability that ${\mathcal{F}}\sim \pi _G^{\mathrm{dis}}$ has a polymer with at least $s$ edges containing the vertex $v$ vertex $v$ . By a union bound, $p_v \leq P_v \;:\!=\; \sum _{\gamma \ni v: |E(\gamma )|\geq s} w_\gamma ^{\mathrm{dis}}$ . Let $\theta = \log (q)/(4 \Delta )$ . By [Reference Helmuth, Jenssen and Perkins21, Equation (13)],

\begin{equation*} \sum _{\gamma \ni v: |\gamma |\gt 1} e^{(1+\theta )|E(\gamma )|} w_\gamma ^{\mathrm {dis}} \leq \tfrac {1}{2}.\end{equation*}

Thus also

\begin{equation*}e^{(1+\theta )s} P_v = e^{(1+\theta )s}\sum _{\gamma \ni v: |E(\gamma )|\geq s} w_\gamma ^{\mathrm {dis}} \leq \sum _{\gamma \ni : |E(\gamma )|\geq s} e^{(1+ \theta )|E(\gamma )|} w_\gamma ^{\mathrm {dis}} \leq \tfrac 12.\end{equation*}

Hence $P_v \leq (1/2) e^{-(1+\theta )s}$ . By a union bound over all vertices, the probability in the statement of the lemma is at most $\sum _v P_v \leq (n/2) 2^{-(1+\theta )s}= (1/2) n^{1-C(1+\theta )}$ . The lemma follows by requiring $q$ to be sufficiently large with respect to $\Delta$ and $C$ that $C(1+\theta ) -1 \geq 3/2$ .

Proof. Note that $\mathrm{Out}({\mathcal{F}}) = \bigcup _{\gamma \in \Gamma ({\mathcal{F}})} E_u(\gamma )$ , so $(\mathrm{e}^\beta -1)^{|E| - \sum _{\gamma \in \Gamma ({\mathcal{F}})}|E_u(\gamma )|} = (\mathrm{e}^\beta -1)^{|{\mathrm{In}}({\mathcal{F}})|}.$ Hence, by [Reference Helmuth, Jenssen and Perkins21, Lemma21], $q^{\sum _{\gamma \in \Gamma ({\mathcal{F}})} c'(\gamma )} = q^{c(G[{\mathrm{In}}({\mathcal{F}})]) - 1}$ , so the result follows.

Proof. This proof closely follows the proof of Proposition 15 from [Reference Helmuth, Jenssen and Perkins21]. Suppose that $q$ is large enough so that $q^{1.9/\Delta }\geq (2\mathrm{e}\Delta )^{400}$ and fix arbitrary $\beta \geq \log (q^{1.9/\Delta }+1)$ .

Consider an arbitrary ordered polymer $\gamma$ . For any configuration ${\mathcal{F}}\in \Omega ^{{\mathrm{ord}}}$ with $\gamma \in \Gamma ({\mathcal{F}})$ , by Lemma27, it holds that $w_G({\mathcal{F}}) \leq q(\mathrm{e}^\beta - 1)^{|E|} w_\gamma ^{\mathrm{ord}}$ . Note that for any ${\mathcal{F}}\in \Omega ^{\mathrm{ord}}$ such that $\gamma \in \Gamma ({\mathcal{F}})$ , there is a configuration ${\mathcal{F}}'$ with $\Gamma ({\mathcal{F}}') = \Gamma ({\mathcal{F}})\setminus \{\gamma \}$ (obtained by setting ${\mathrm{In}}({\mathcal{F}}') ={\mathrm{In}}({\mathcal{F}})\cup E_u(\gamma )$ ), which therefore has weight $w_G({\mathcal{F}}') = w_G({\mathcal{F}})/w_\gamma ^{\mathrm{ord}}$ .

Let $\Omega _\gamma$ be the set of all ordered configurations with a polymer $\gamma$ . We can lower bound $Z^{\mathrm{ord}}$ by $\sum _{{\mathcal{F}}\in \Omega _\gamma } (w_G({\mathcal{F}}) + w_G({\mathcal{F}}')) = (1 + \frac{1}{w_\gamma ^{\mathrm{ord}}}) \sum _{{\mathcal{F}}\in \Omega _\gamma } w_G({\mathcal{F}})$ . Therefore,

\begin{equation*} \pi ^{\mathrm {ord}}(\gamma \in \Gamma (\cdot )) = \frac {\sum _{{\mathcal {F}}\in \Omega _\gamma } w_G({\mathcal {F}})}{Z^{\mathrm {ord}}} \leq \frac {1}{1 + \frac {1}{w_\gamma ^{\mathrm {ord}}}}\leq w_\gamma ^{\mathrm {ord}}, \end{equation*}

so we conclude that the probability that any fixed polymer $\gamma$ is a polymer of ${\mathcal{F}}\sim \pi ^{\mathrm{ord}}_G$ is at most $w_\gamma ^{\mathrm{ord}}$ .

Let $u$ be a vertex in $V(G)$ and denote by $\Gamma _u$ the set of polymers containing $u$ . Let $p_u$ be the probability that $u$ is contained in a polymer of size at least $s$ for ${\mathcal{F}}\sim \pi ^{\mathrm{ord}}_G$ . By a union bound over the polymers in $\Gamma _u$ , We have that $p_u\leq P_u$ , where

\begin{equation*} P_u\;:\!=\; \sum _{\gamma \in \Gamma _u;\ |E(\gamma )|\geq s} w_\gamma ^{\mathrm {ord}} \end{equation*}

By [Reference Helmuth, Jenssen and Perkins21, Lemma 14], $c'(\gamma )\leq 9|E_u(\gamma )|/(5 \Delta )$ . The bound on $\beta$ ensures that

\begin{equation*}w_\gamma ^{\mathrm {ord}} = q^{c'(\gamma )} (\mathrm {e}^\beta -1)^{-|E_u(\gamma )|} \leq (\mathrm {e}^\beta -1)^{(\frac {9}{5\Delta }\cdot \frac {\Delta }{1.9} - 1)|E_u(\gamma )|}\leq (\mathrm {e}^\beta -1)^{-|E_u(\gamma )|/20}.\end{equation*}

Hence we get

\begin{equation*} P_u \leq \sum _{\gamma \in \Gamma _u;\ |E(\gamma )|\geq s} (\mathrm {e}^\beta -1)^{-|E_u(\gamma )|/20}. \end{equation*}

By [Reference Helmuth, Jenssen and Perkins21, Lemma 12], for any ordered polymer $\gamma$ , $|E(\gamma )|\leq 10|E_u(\gamma )|$ . Thus

\begin{equation*} P_u \leq \sum _{k\geq s/10}\ \ \sum _{\gamma \in \Gamma _u;\ |E_u(\gamma )| = k} (\mathrm {e}^\beta -1)^{-|E_u(\gamma )|/20}. \end{equation*}

By [Reference Helmuth, Jenssen and Perkins21, Proof of Proposition 15], the number of polymers with $k$ unoccupied edges containing a particular vertex is at most $(2\mathrm{e}\Delta )^{10k}$ , hence

\begin{equation*} P_u\leq \sum _{k\geq s/10}\big ((2\mathrm {e}\Delta )^{10}(\mathrm {e}^{\beta }-1)^{-1/20}\big )^{k}.\end{equation*}

By the lower bounds on $\beta$ and $q$ , we have $\mathrm{e}^{\beta }-1\geq q^{1.9/\Delta }\geq (2\mathrm{e}\Delta )^{400}$ so

\begin{equation*} P_u\leq \sum _{k\geq s/10} (\mathrm {e}^{\beta }-1)^{-k/40} \leq \sum _{k\geq s/10} \mathrm {e}^{-\beta k/80}.\end{equation*}

The last sum is a geometric series with ratio $\mathrm{e}^{-\beta /80}\lt 1/2$ , so it is upper bounded by twice its largest term. Since $s=\tfrac{2000}{\beta }\log n$ , it follows that $P_u\leq 2/n^{5/2}$ . By a union bound over the vertices of $G$ , the probability that there is a polymer of ${\mathcal{F}}\sim \pi ^{{\mathrm{ord}}}_G$ which has size at least $s$ is therefore at most $2/n^{3/2}$ , as required.

Proof. We start with the proof of Item 1. Consider a non-giant component $\kappa '$ of $G[{\mathrm{In}}({\mathcal{F}})]$ . Let $\tau$ be the set of vertices in $\kappa '$ which have an incident edge that is not in a polymer of $\mathcal{F}$ . For contradiction, assume that $\tau$ is non-empty. By Corollary20, $|\kappa '|\leq \delta |V|$ and thus $|\tau |\leq \delta |V|$ . The definition of $\tau$ and the fact that out-edges are in polymers imply that every edge in the cut $(\tau, V\backslash \tau )$ is in some polymer. By the expansion properties $|E(\tau, V \backslash \tau )|\geq 5\Delta |\tau |/9$ , hence there is a vertex $u\in \tau$ with at least ${5\Delta }/{9}$ incident edges in the cut, and thus, from the definition of polymers, all edges adjacent to $u$ are in polymers, contradicting that $u$ is in $\tau$ .

Before proving Item 2, we use it to prove Item 3. Let $\kappa '$ be a non-giant component in $G[{\mathrm{In}}({\mathcal{F}})\backslash S]$ . As before, let $\tau$ be the set of vertices in $\kappa '$ which have an incident edge that is not in a polymer of $\mathcal{F}$ . By Item 2, $|\tau | \leq 45\Delta |S|$ . Let $E_\tau$ be the set of edges that are incident to vertices in $\tau$ . Note that $G[V(\kappa '),E(\kappa ')]$ is connected, and removing an edge from a graph can increase the number of components by at most one. Thus, $(V(\kappa '),E(\kappa ')\setminus E_\tau )$ has at most $1+\Delta |\tau |$ components. Any edges in these components are in polymers of $\mathcal{F}$ . Thus there are at most $1 + \Delta |\tau | \leq 50\Delta ^2|S|$ components of $G[{\mathcal{B}}_\infty (\mathrm{Out}({\mathcal{F}}))]$ that contain vertices in $V(\kappa ')$ , proving Item 3.

To finish, we prove Item 2. First we bound the size of $\kappa '$ . Since ${\mathcal{F}} \in \Omega ^{\mathrm{ord}}$ , $|{\mathrm{In}}({\mathcal{F}})\backslash S| \geq (1 - \eta ) |E| - |S|$ . Since $\eta \leq 1/100$ , $\eta + \frac{|S|}{|E|} \lt 1/10 \leq \phi _G(1/2)$ , hence we can apply Lemma17 with $E' = \mathrm{Out}({\mathcal{F}}) \cup S$ and $\theta = |E'|/|E|$ . We find that $(V,{\mathrm{In}}({\mathcal{F}}) \backslash S)$ has a component of size at least $(1 - \frac{\theta }{2 \phi _G(1/2)}) n \geq (1 -{5 \theta } ) n$ so the number of vertices in $\kappa '$ is at most $5 \theta n \leq 5(\eta + |S|/|E|)n \leq \delta n + 10|S|/\Delta$ . Thus, $|\tau | \leq \delta n + 10 |S|/\Delta$ . Next let $\lambda = \lceil 10 |S|/\Delta \rceil$ and let $U$ be a subset of $\tau$ of size $|\tau | - \lambda \leq \delta n$ . Then

\begin{align*} |E(\tau, V\backslash \tau )| &\geq |E(U,V\setminus \tau )| \\[5pt] &\geq |E(U,V\setminus U)| - |E(U,\tau \setminus U)|\\[5pt] &\geq \tfrac 59 \Delta |U| - \lambda \Delta = \tfrac 59 \Delta |\tau | - 14 \lambda \Delta /9. \end{align*}

By the definition of $\tau$ , all edges in $E(\tau, V(\kappa ')\setminus \tau )$ are in polymers of $\mathcal{F}$ . Since $\kappa '$ is a component of $G[{\mathrm{In}}({\mathcal{F}})\setminus S]$ , there are at most $|S|$ edges in ${\mathrm{In}}({\mathcal{F}})$ between $\tau$ and $V\setminus V(\kappa ')$ . Thus the number of edges in $E(\tau, V\setminus \tau )$ that are in polymers is at least $|E(\tau, V\backslash \tau )| - |S|$ . This is at least $\tfrac 59 \Delta |\tau | - 14 \lambda \Delta /9 - |S| \geq \tfrac 59 \Delta |\tau | - 149 |S|/9 - 14\Delta /9 \geq \tfrac 59 \Delta |\tau | - 45 \Delta |S|/9$ , where the last inequality follows from $\Delta \geq 5$ , $|S|\geq 1$ .

Averaged over all vertices $w\in \tau$ , the number of edges in $E(\tau, V\setminus \tau )$ that are in polymers and are incident to $w$ is at least $\tfrac 59 \Delta - 45 \Delta |S|/(9\tau )$ . We may assume $\tau$ is non-empty, otherwise Item 2 directly follows. Thus, there is a vertex $w\in \tau$ such that the number of edges in $E(\tau, V\setminus \tau )$ that are in polymers and are incident to $w$ is at least $\tfrac 59 \Delta - 45 \Delta |S|/(9\tau )$ . Since this number is an integer, the number of edges in $E(\tau, V\setminus \tau )$ that are in polymers and are incident to $w$ is at least

\begin{equation*} W \;:\!=\; \Big \lceil \frac 59 \Delta - \frac {45\Delta |S|}{9|\tau |}\Big \rceil . \end{equation*}

Suppose for contradiction that $|\tau | \gt 45\Delta |S|$ . Then the term that is subtracted in the definition of $W$ is less than $1/9$ . On the other hand, if the first term, $5\Delta /9$ is not an integer, then its non-integer part is at least $1/9$ . Either way, $W = \lceil 5 \Delta /9\rceil \geq 5\Delta /9$ . As in the proof of Item 1, all incident edges of $w$ hence must be a in a polymer, contradicting that $w\in \tau$ .

Proof. We do an induction on $i$ . For the base case let $i = 0$ . Inv1( $0$ ) holds by the definitions of $F_0$ , ${\mathcal{F}}_0^{\mathrm{ord}}$ and ${\mathcal{F}}_0^+$ . Inv2( $0$ ) follows from the fact that any $u\in V_0$ is a leaf of $T$ and thus $T_u$ contains a single vertex - $u$ .

The second part of Inv3( $0$ ) is trivial as neither of the subtrees have any edges. We show the first part of Inv3( $0$ ) by proving that for all $u\in V(T)$ , $u\in V_0$ if and only if $u\in V(F_0)$ . First, suppose that $u\in V(F_0)\cap V(T)$ . The definitions of $F_0$ and $T$ imply that $d_G(u,v) = r_1$ so $u\in V_0$ , as desired. For the other direction, consider $u\in V_0$ . We need to show that $G$ has an edge $\{u,u'\}$ with $d_G(u',v) \gt r_1$ . The vertex $u$ is a leaf of $T$ , hence $u$ has a single incident edge in $E(T)$ . Given that $G$ is $\Delta$ -regular with $\Delta \gt 1$ , there is some edge $\{u, u'\}$ , such that $u'$ is not $u$ ’s parent in $T$ . By Observation32, $d_G(u', v) \in \{r_1 - 1, r_1, r_1 + 1\}$ . By the choice of $r_1$ , $ r_2$ , and $u'$ , $\{u, u'\} \notin E(B_{r_1}(v))\setminus E(B_{r_2}(v))$ , so $d_G(u', v) = r_1 + 1 \gt r_1$ , and the result follows.

The invariant Inv4( $0$ ) follows from the fact that for any $u\in \partial _G (F_0)$ there are edges $\{u, u_1\} \in F_0$ and $\{u,u_2\}\notin F_0$ , so $d_G(u, v) \leq r_1$ and $d_G(u_2, v) \leq r_1$ , and thus also $d_G(u_1, v) \gt r_1$ , so by Observation32 it follows that $d_G(u, v) = r_1$ and thus $u\in V_0$ .

For the inductive step, suppose $F_{i+1}$ , ${\mathcal{F}}_{i+1}^{\mathrm{ord}}$ , $F_{i+1}^+$ and $V_{i+1}$ are all defined and suppose that Inv1( $i$ )-Inv4( $i$ ) hold. We now show Inv5( $i$ ), Inv6( $i$ ) and Inv1( $i+1$ )–Inv4( $i+1$ ).

For Inv5( $i$ ), $F_{i}\subseteq F_{i+1}$ follows by construction. For the strict inequality, it is enough to show that $\{w_i, p_i\}\in F_{i+1}\setminus F_i$ . Since $F_{i+1}$ is defined, $d_G(F_i, v) \gt r_2$ , otherwise the process would terminate before the $(i+1)$ th iteration of Step 3. Thus by Inv4( $i$ ) and by $w_i\in \partial _G (F_i)$ , $w_i\in V_i$ . So for any $u\in V_i$ , Inv2( $i$ ) implies that $p_i\notin V(T_u)$ . Hence Inv3( $i$ ) implies that $p_i\notin V(F_i)$ so $\{w_i, p_i\}\notin F_i$ . But $E(T_{p_i})\subseteq F_{i+1}$ , hence $\{w_i, p_i\}\in F_{i+1}$ , completing the proof of Inv5( $i$ ). Inv6( $i$ ) follows by construction.

The first and third parts of Inv1( $i+1$ ) follow by construction, the second part follows from Corollary53 (see Appendix B, using ${\mathrm{In}}({\mathcal{F}}_i^{\mathrm{ord}})\subseteq{\mathrm{In}}({\mathcal{F}}_i^+)$ and the fact that the coupling is optimal. Inv2( $i + 1$ ) follows by construction and Inv2( $i$ ). Also, the second part of Inv3( $i + 1$ ) follows by construction and Inv3( $i$ ).

For the first part of Inv3( $i+1$ ), by the definition of $F_{i+1}$ , if $u\in V(F_{i+1})\cap V(T)$ , then $u\in V(T_{p_i})$ or $u\in V(F_{i})\cap V(T)$ . In the first case, note $p_i\in V_{i+1}$ . Otherwise, by Inv3( $i$ ), there is a vertex $u'\in V_i$ with $u\in V(T_{u'})$ . If $u'$ is in $V(T_{p_i})$ , then so is $u$ , hence the first case applies. If not, then $u'\in V_{i+1}$ . For the converse, for $u\in V_{i+1}$ , there are two cases. If $u = p_i$ then $E(T_{p_i})\subseteq F_{i+1}$ so $V(T_{p_i}) \subseteq V(F_{i+1})\cap V(T)$ . Otherwise, $u\in V_i$ , so the result follows by Inv3( $i$ ) and Inv5( $i$ ).