The Critical Mean-field Chayes-Machta Dynamics

Antonio Blanca Pennsylvania State University. Email: [email protected]. Research supported in part by NSF grant CCF-1850443. Alistair Sinclair UC Berkeley. Email: [email protected]. Research supported in part by NSF grant CCF-1815328. Xusheng Zhang Pennsylvania State University. Email: [email protected]. Research supported in part by NSF grant CCF-1850443.

Abstract

The random-cluster model is a unifying framework for studying random graphs, spin systems and electrical networks that plays a fundamental role in designing efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the classical ferromagnetic Ising and Potts models.

In this paper, we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, where the underlying graph is the complete graph on $n$ vertices. The random-cluster model is parametrized by an edge probability $p$ and a cluster weight $q$ . Our focus is on the critical regime: $p=p_{c}(q)$ and $q\in(1,2)$ , where $p_{c}(q)$ is the threshold corresponding to the order-disorder phase transition of the model. We show that the mixing time of the Chayes-Machta dynamics is $O(\log n\cdot\log\log n)$ in this parameter regime, which reveals that the dynamics does not undergo an exponential slowdown at criticality, a surprising fact that had been predicted (but not proved) by statistical physicists. This also provides a nearly optimal bound (up to the $\log\log n$ factor) for the mixing time of the mean-field Chayes-Machta dynamics in the only regime of parameters where no non-trivial bound was previously known. Our proof consists of a multi-phased coupling argument that combines several key ingredients, including a new local limit theorem, a precise bound on the maximum of symmetric random walks with varying step sizes, and tailored estimates for critical random graphs.

In addition, we derive an improved comparison inequality between the mixing time of the Chayes-Machta dynamics and that of the local Glauber dynamics on general graphs; this results in better mixing time bounds for the local dynamics in the mean-field setting.

1 Introduction

The random-cluster model generalizes classical random graph and spin system models, providing a unifying framework for their study [14]. It plays an indispensable role in the design of efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the ferromagnetic Ising/Potts model [31, 8, 20] and has become a fundamental tool in the study of phase transitions [2, 12, 11].

The random-cluster model is defined on a finite graph $G=(V,E)$ with an edge probability parameter $p\in(0,1)$ and a cluster weight $q>0$ . The set of configurations of the model is the set of all subsets of edges $A\subseteq E$ . The probability of each configuration $A$ is given by the Gibbs distribution:

\mu_{G,p,q}(A)=\frac{1}{Z}\cdot p^{|A|}(1-p)^{|E|-|A|}q^{c(A)};

(1)

where $c(A)$ is the number of connected components in $(V,A)$ and $Z:=Z(G,p,q)$ is the normalizing factor called the partition function.

The special case when $q=1$ corresponds to the independent bond percolation model, where each edge of the graph $G$ appears independently with probability $p$ . Independent bond percolation is also known as the Erdős-Rényi random graph model when $G$ is the complete graph.

For integer $q\geq 2$ , the random-cluster model is closely related to the ferromagnetic $q$ -state Potts model. Configurations in the $q$ -state Potts model are the assignments of spin values $\{1,\dots,q\}$ to the vertices of $G$ ; the $q=2$ case corresponds to the Ising model. A sample $A\subseteq E$ from the random-cluster distribution can be easily transformed into one for the Ising/Potts model by independently assigning a random spin from $\{1,\dots,q\}$ to each connected component of $(V,A)$ . Random-cluster based sampling algorithms, which include the widely-studied Swendsen-Wang dynamics [30], are an attractive alternative to Ising/Potts Markov chains since they are often efficient at “low-temperatures” (large $p$ ). In this parameter regime, several standard Ising/Potts Markov chains are known to converge slowly.

In this paper we investigate the Chayes-Machta (CM) dynamics [10], a natural Markov chain on random-cluster configurations that converges to the random-cluster measure. The CM dynamics is a generalization to non-integer values of $q$ of the widely studied Swendsen-Wang dynamics [30]. As with all applications of the MCMC method, the primary object of study is the mixing time, i.e., the number of steps until the dynamics is close to its stationary distribution, starting from the worst possible initial configuration. We are interested in understanding how the mixing time of the CM dynamics grows as the size of the graph $G$ increases, and in particular how it relates to the phase transition of the model.

Given a random-cluster configuration $(V,A)$ , one step of the CM dynamics is defined as follows:

(i)

activate each connected component of $(V,A)$ independently with probability $1/q$ ;
(ii)

remove all edges connecting active vertices;
(iii)

add each edge between active vertices independently with probability $p$ , leaving the rest of the configuration unchanged.

We call (i) the activation sub-step, and (ii) and (iii) combined the percolation sub-step. It is easy to check that this dynamics is reversible with respect to the Gibbs distribution (1) and thus converges to it [10]. For integer $q$ , the CM dynamics may be viewed as a variant of the Swendsen-Wang dynamics. In the Swendsen-Wang dynamics, each connected component of $(V,A)$ receives a random color from $\{1,\dots,q\}$ , and the edges are updated within each color class as in (ii) and (iii) above; in contrast, the CM dynamics updates the edges of exactly one color class. However, note that the Swendsen-Wang dynamics is only well-defined for integer $q$ , while the CM dynamics is feasible for any real $q>1$ . Indeed, the CM dynamics was introduced precisely to allow this generalization.

The study of the interplay between phase transitions and the mixing time of Markov chains goes back to pioneering work in mathematical physics in the late 1980s. This connection for the specific case of the CM dynamics on the complete $n$ -vertex graph, known as the mean-field model, has received some attention in recent years (see [7, 15, 18]) and is the focus of this paper. As we shall see, the mean-field case is already quite non-trivial, and has historically proven to be a useful starting point in understanding various types of dynamics on more general graphs. We note that, so far, the mean-field is the only setting in which there are tight mixing time bounds for the CM dynamics; all other known bounds are deduced indirectly via comparison with other Markov chains, thus incurring significant overhead [8, 6, 17, 5, 31, 7].

The phase transition for the mean-field random-cluster model is fairly well-understood [9, 25]. In this setting, it is natural to re-parameterize by setting $p=\zeta/n$ ; the phase transition then occurs at the critical value $\zeta=\zeta_{\textnormal{{cr}}}(q)$ , where $\zeta_{\textnormal{{cr}}}(q)=q$ when $q\in(0,2]$ and $\zeta_{\textnormal{{cr}}}(q)=2(\frac{q-1}{q-2})\log(q-1)$ for $q>2$ . For $\zeta<\zeta_{\textnormal{{cr}}}(q)$ all components are of size $O(\log n)$ with high probability (w.h.p.); that is, with probability tending to $1$ as $n\rightarrow\infty$ . This regime is known as the disordered phase. On the other hand, for $\zeta>\zeta_{\textnormal{{cr}}}(q)$ there is a unique giant component of size $\approx\theta n$ , where $\theta=\theta(\zeta,q)$ ; this regime of parameters is known as the ordered phase. The phase transition is thus analogous to that in $G(n,p)$ corresponding to the emergence of a giant component.

The phase structure of the mean-field random-cluster model, however, is more subtle and depends crucially on the second parameter $q$ . In particular, when $q>2$ the model exhibits phase coexistence at the critical threshold $\zeta=\zeta_{\textnormal{{cr}}}(q)$ . Roughly speaking, this means that when $\zeta=\zeta_{\textnormal{{cr}}}(q)$ , the set of configurations with all connected components of size $O(\log n)$ , and set of configurations with a unique giant component, contribute each a constant fraction of the probability mass. For $q\leq 2$ , on the other hand, there is no phase coexistence. These subtleties are illustrated in Figure 1.

(a)

q>2

(b)

1<q\leq 2

Figure 1: (a)): phase structure when

q>2

. (b): phase structure when

q\in(1,2]

Phase coexistence at $\zeta=\zeta_{\textnormal{{cr}}}(q)$ when $q>2$ has significant implications for the speed of convergence of Markov chains, including the CM dynamics. The following detailed connection between the phase structure of the model and the mixing time $\tau_{\rm mix}^{\mathrm{CM}}$ of the CM dynamics was recently established in [7, 4, 18]. When $q>2$ , we have:

\tau_{\rm mix}^{\mathrm{CM}}=\begin{cases}\Theta(\log n)&\textrm{if}~{}\zeta\not\in[\zeta_{\textsc{l}},\zeta_{\textsc{r}});\\ \Theta(n^{1/3})&\textrm{if}~{}\zeta=\zeta_{\textsc{l}};\\ e^{\Omega({n})}&\textrm{if}~{}\zeta\in(\zeta_{\textsc{l}},\zeta_{\textsc{r}}),\end{cases}

(2)

where $(\zeta_{\textsc{l}},\zeta_{\textsc{r}})$ is the so-called metastability window. It is known that $\zeta_{\textsc{r}}=q$ , but $\zeta_{\textsc{l}}$ does not have a closed form; see [7, 25]; we note that $\zeta_{\textnormal{{cr}}}(q)\in(\zeta_{\textsc{l}},\zeta_{\textsc{r}})$ for $q>2$ .

When $q\in(1,2]$ , there is no metastability window, and the mixing time of the mean-field CM dynamics is $\Theta(\log n)$ for all $\zeta\neq\zeta_{\textnormal{{cr}}}(q)$ . In view of these results, the only case remaining open is when $q\in(1,2]$ and $\zeta=\zeta_{\textnormal{{cr}}}(q)$ . Our main result shown below concerns precisely this regime, which is particularly delicate and had resisted analysis until now for reasons we explain in our proof overview.

Theorem 1.1.

The mixing time of the CM dynamics on the complete $n$ -vertex graph when $\zeta=\zeta_{\textnormal{{cr}}}(q)=q$ and $q\in(1,2)$ is $O(\log n\cdot\log\log n)$ .

A $\Omega(\log n)$ lower bound is known for the mixing time of the mean-field CM dynamics that holds for all $p\in(0,1)$ and $q>1$ [7]. Therefore, our result is tight up to the lower order $O(\log\log n)$ factor, and in fact even better as we explain in Remark 4. The conjectured tight bound when $\zeta=\zeta_{\textnormal{{cr}}}(q)$ and $q\in(1,2)$ is $\Theta(\log n)$ . We mention that the $\zeta=\zeta_{\textnormal{{cr}}}(q)$ and $q=2$ case, which is quite different and not covered by Theorem 1.1, was considered earlier in [24] for the closely related Swendsen-Wang dynamics, and a tight $\Theta(n^{1/4})$ bound was established for its mixing time. The same mixing time bound is expected for the CM dynamics in this regime.

Our result establishes a striking behavior for random-cluster dynamics when $q\in(1,2)$ . Namely, there is no slowdown (exponential or power law) in this regime at the critical threshold $\zeta=\zeta_{\textnormal{{cr}}}(q)$ . Note that for $q>2$ , as described in (2) above, the mixing time of the dynamics undergoes an exponential slowdown, transitioning from $\Theta(\log n)$ when $\zeta<\zeta_{\textsc{l}}$ , to a power law at $\zeta=\zeta_{\textsc{l}}$ , and to exponential in $n$ when $\zeta\in(\zeta_{\textsc{l}},\zeta_{\textsc{r}})$ . The absence of a critical slowdown for $q\in(1,2)$ was in fact predicted by the statistical physics community [16], and our result provides the first rigorous proof of this phenomenon. See Remark 1 for further comments.

Our second result concerns the local Glauber dynamics for the random-cluster model. In each step, the Glauber dynamics updates a single edge of the current configuration chosen uniformly at random; a precise definition of this Markov chain is given in Section 6. In [7], it was established that any upper bound on the mixing time $\tau_{\rm mix}^{\mathrm{CM}}$ of the CM dynamics can be translated to one for the mixing time $\tau_{\rm mix}^{\mathrm{GD}}$ of the Glauber dynamics, at the expense of a $\tilde{O}(n^{4})$ factor; the $\tilde{O}$ notation hides polylogarithmic factors. In particular, it was proved in [7] that $\tau_{\rm mix}^{\mathrm{GD}}\leq\tau_{\rm mix}^{\mathrm{CM}}\cdot\tilde{O}(n^{4}).$ We provide here an improvement of this comparison inequality.

Theorem 1.2.

For all $q>1$ and all $\zeta=O(1)$ , $\tau_{\rm mix}^{\mathrm{GD}}\leq\tau_{\rm mix}^{\mathrm{CM}}\cdot{O}(n^{3}(\log n)^{2}).$

To prove this theorem, we establish a general comparison inequality that holds for any graph, any $q\geq 1$ and any $p\in(0,1)$ ; see Theorem 6.1 for a precise statement. When combined with the known mixing time bounds for the CM dynamics on the complete graph, Theorem 1.2 yields that the random-cluster Glauber dynamics mixes in $\tilde{O}(n^{3})$ steps when $q>2$ and $\zeta\not\in(\zeta_{\textsc{l}},\zeta_{\textsc{r}})$ , or when $q\in(1,2)$ and $\zeta=O(1)$ . In these regimes, the mixing time of the Glauber dynamics was previously known to be $\tilde{O}(n^{4})$ and is conjectured to be $\tilde{O}(n^{2})$ ; the improved comparison inequality in Theorem 1.2 gets us closer to this conjectured tight bound. We note, however, that even if one showed the conjectured optimal bound for the mixing time of the Glauber dynamics, the CM is faster, even if we take into account the computational cost associated to implementing its steps.

We conclude this introduction with some brief remarks about our analysis techniques, which combine several key ingredients in a non-trivial way. Our bound on the mixing time uses the well-known technique of coupling: in order to show that the mixing time is $O(\log n\cdot\log\log n)$ , it suffices to couple the evolutions of two copies of the dynamics, starting from two arbitrary configurations, in such a way that they arrive at the same configuration after $O(\log n)$ steps with probability $\Omega(1/\log\log n)$ . (The moves of the two copies can be correlated any way we choose, provided that each copy, viewed in isolation, is a valid realization of the dynamics.) Because of the delicate nature of the phase transition in the random-cluster model, combined with the fact that the percolation sub-step of the CM dynamics is critical when $\zeta=q$ , our coupling is somewhat elaborate and proceeds in multiple phases. The first phase consists of a burn-in period, where the two copies of the chain are run independently and the evolution of their largest components is observed until they have shrunk to their “typical” sizes. This part of the analysis is inspired by similar arguments in earlier work [7, 24, 15].

In the second phase, we design a coupling of the activation of the connected components of the two copies which uses: (i) a local limit theorem, which can be thought of as a stronger version of a central limit theorem; (ii) a precise understanding of the distribution of the maximum of symmetric random walks on $\mathbb{Z}$ with varying step sizes; and (iii) precise estimates for the component structure of random graphs. We develop tailored versions of these probabilistic tools for our setting and combine them to guarantee that the same number of vertices from each copy are activated in each step w.h.p. for sufficiently many steps. This phase of the coupling is the main novelty in our analysis, and allows us to quickly converge to the same configuration. We give a more detailed overview of our proof in the following section.

2 Proof sketch and techniques

We now give a detailed sketch of the multi-phased coupling argument for proving Theorem 1.1. We start by formally defining the notions of mixing and coupling times. Let $\Omega_{\textsc{\tiny RC}}$ be the set of random-cluster configurations of a graph $G$ ; let $\mathcal{M}$ be the transition matrix of a random-cluster Markov chain with stationary distribution $\mu=\mu_{G,p,q}$ , and let $\mathcal{M}^{t}(X_{0},\cdot)$ be the distribution of the chain after $t$ steps starting from $X_{0}\in\Omega_{\textsc{\tiny RC}}$ . The $\varepsilon$ -mixing time of $\mathcal{M}$ is given by

\tau_{\rm mix}^{\mathcal{M}}(\varepsilon):=\max\limits_{X_{0}\in\Omega_{\textsc{\tiny RC}}}\min\limits_{t\geq 0}\left\{||\mathcal{M}^{t}(X_{0},\cdot)-\mu(\cdot)||_{\textsc{\tiny TV}}\leq\varepsilon\right\},

where $||\cdot||_{\textsc{\tiny TV}}$ denotes total variation distance. In particular, the mixing time of $\mathcal{M}$ is $\tau_{\rm mix}^{\mathcal{M}}:=\tau_{\rm mix}^{\mathcal{M}}(1/4)$ .

A (one step) coupling of the Markov chain $\mathcal{M}$ specifies, for every pair of states $(X_{t},Y_{t})\in\Omega_{\textsc{\tiny RC}}\times\Omega_{\textsc{\tiny RC}}$ , a probability distribution over $(X_{t+1},Y_{t+1})$ such that the processes $\{X_{t}\}$ and $\{Y_{t}\}$ are valid realizations of $\mathcal{M}$ , and if $X_{t}=Y_{t}$ then $X_{t+1}=Y_{t+1}$ . The coupling time, denoted $T_{\rm coup}$ , is the minimum $T$ such that $\Pr[X_{T}\neq Y_{T}]\leq 1/4$ , starting from the worst possible pair of configurations in $\Omega_{\textsc{\tiny RC}}$ . It is a standard fact that $\tau_{\rm mix}^{\mathcal{M}}\leq T_{\rm coup}$ ; moreover, when $\Pr[X_{T}=Y_{T}]\geq\delta$ for some coupling, then $\tau_{\rm mix}^{\mathcal{M}}=O(T\delta^{-1})$ (see, e.g., [22]).

We provide first a high level description of our coupling for the CM dynamics. For this, we require the following notation. For a random cluster configuration $X$ , let $L_{i}(X)$ denote the size of the $i$ -th largest connected component in $(V,X)$ , and let $\mathcal{R}_{i}(X):=\sum_{j\geq i}L_{j}(X)^{2}$ ; in particular, $\mathcal{R}_{1}(X)$ is the sum of the squares of the sizes of all the components of $(V,X)$ . Our coupling has three main phases:

1.

Burn-in period: run two copies $\{X_{t}\}$ , $\{Y_{t}\}$ independently, starting from a pair of arbitrary initial configurations, until $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ and $\mathcal{R}_{1}(Y_{T})=O(n^{4/3})$ .
2.
Coupling to the same component structure: starting from $X_{T}$ and $Y_{T}$ such that $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ and $\mathcal{R}_{1}(Y_{T})=O(n^{4/3})$ , we design a two-phased coupling that reaches two configurations with the same component structure as follows:
1. 2a.
  
  A two-step coupling after which the two configurations agree on all “large components”;
2. 2b.
  
  A coupling that after $O(\log n)$ additional steps reaches two configurations that will also have the same “small component” structure.
3.

Coupling to the same configuration: starting from two configurations with the same component structure, there is a straightforward coupling that couples the two configurations in $O(\log n)$ steps w.h.p.

We proceed to describe each of these phases in detail.

2.1 The burn-in period

During the initial phase, two copies of the dynamics evolve independently. This is called a burn-in period and in our case consists of three sub-phases.

In the first sub-phase of the burn-in period the goal is to reach a configuration $X$ such that $\mathcal{R}_{2}(X)=O(n^{4/3})$ . For this, we use a lemma from [4], which shows that after $T=O(\log n)$ steps of the CM dynamics $\mathcal{R}_{2}(X_{T})=O(n^{4/3})$ with at least constant probability; this holds when $\zeta=q$ for any initial configuration $X_{0}$ and any $q>1$ .

Lemma 2.1 ([4], Lemma 3.42).

Let $q>1$ and $\zeta=q$ , and let $X_{0}$ be an arbitrary random-cluster configuration. Then, for any constant $C\geq 0$ , after $T=O(\log n)$ steps $\mathcal{R}_{2}(X_{T})=O(n^{4/3})$ and $L_{1}(X_{T})>Cn^{2/3}$ with probability $\Omega(1)$ .

In the second and third sub-phases of the burn-in period, we use the fact that when $\mathcal{R}_{2}(X_{t})=O(n^{4/3})$ , the number of activated vertices is well concentrated around $n/q$ (its expectation). This is used to show that the size of the largest component contracts at a constant rate for $T=O(\log n)$ steps until a configuration $X_{T}$ is reached such that $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ . This part of the analysis is split into two sub-phases because the contraction for $L_{1}(X_{t})$ requires a more delicate analysis when $L_{1}(X_{t})=o(n)$ ; this is captured in the following two lemmas.

Lemma 2.2.

Let $\zeta=q$ and $q\in(1,2)$ . Suppose $\mathcal{R}_{2}(X_{0})=O(n^{4/3})$ . Then, for any constant $\delta>0$ , there exists $T=T(\delta)=O(1)$ such that $\mathcal{R}_{2}(X_{T})=O(n^{4/3})$ and ${L_{1}}(X_{T})\leq\delta n$ with probability $\Omega(1)$ .

Lemma 2.3.

Let $\zeta=q$ and $q\in(1,2)$ . Suppose $\mathcal{R}_{2}(X_{0})=O(n^{4/3})$ and that $L_{1}(X_{0})\leq\delta n$ for a sufficiently small constant $\delta$ . Then, with probability $\Omega(1)$ , after $T=O(\log n)$ steps $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ .

Lemmas 2.2 and 2.3 are proved in Section 4. Combining them with Lemma 2.1 immediately yields the following theorem.

Theorem 2.4.

Let $\zeta=q$ , $q\in(1,2)$ and let $X_{0}$ be an arbitrary random-cluster configuration of the complete $n$ -vertex graph. Then, with probability $\Omega(1)$ , after $T=O(\log n)$ steps $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ .

Remark 1.

The contraction of $L_{1}(X_{t})$ established by Lemmas 2.2 and 2.3 only occurs when $q\in(1,2)$ ; when $q>2$ the quantity $L_{1}(X_{t})$ may increase in expectation, whereas for $q=2$ we have $\operatorname*{{\rm E}}[L_{1}(X_{t+1})\mid X_{t}]\approx L_{1}(X_{t})$ , and the contraction of the size of the largest component is due instead to fluctuations caused by a large second moment. (This is what causes the power law slowdown when $\zeta=q=2$ .)

Remark 2.

Sub-steps (ii) and (iii) of the CM dynamics are equivalent to replacing the active portion of the configuration by a $G(m,q/n)$ random graph, where $m$ is the number of active vertices. Since $\operatorname*{{\rm E}}[m]=n/q$ , one key challenge in the proofs of Lemmas 2.2 and 2.3, and in fact in the entirety of our analysis, is that the random graph $G(m,q/n)$ is critical or almost critical w.h.p. since $m\cdot q/n\approx 1$ ; consequently its structural properties are not well concentrated and cannot be maintained for the required $O(\log n)$ steps of the coupling. This is one of the key reasons why the $\zeta=\zeta_{\textnormal{{cr}}}(q)=q$ regime is quite delicate.

2.2 Coupling to the same component structure

For the second phase of the coupling, we assume that we start from a pair of configurations $X_{0}$ , $Y_{0}$ such that $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ , $\mathcal{R}_{1}(Y_{0})=O(n^{4/3})$ . The goal is to show that after $T=O(\log n)$ steps, with probability $\Omega(1/\log\log n)$ , we reach two configurations $X_{T}$ and $Y_{T}$ with the same component structure; i.e., $L_{j}(X_{T})=L_{j}(Y_{T})$ for all $j\geq 1$ . In particular, we prove the following.

Theorem 2.5.

Let $\zeta=q$ , $q\in(1,2)$ and suppose $X_{0},Y_{0}$ are random-cluster configurations such that $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ and $\mathcal{R}_{1}(Y_{0})=O(n^{4/3})$ . Then, there exists a coupling of the CM steps such that after $T=O(\log n)$ steps $X_{T}$ and $Y_{T}$ have the same component structure with probability $\Omega\left((\log\log n)^{-1}\right)$ .

Our coupling construction for proving Theorem 2.5 has two main sub-phases. The first is a two-step coupling after which the two configurations agree on all the components of size above a certain threshold $B_{\omega}={n^{2/3}}/{\omega(n)}$ , where $\omega(n)$ is a slowly increasing function. For convenience and definiteness we set $\omega(n)=\log\log\log\log n$ . In the second sub-phase we take care of matching the small component structures.

We note that when the same number of vertices are activated from each copy of the chain, we can easily couple the percolation sub-step (with an arbitrary bijection between the activated vertices) and replace the configuration on the active vertices in both chains with the same random sub-graph; consequently, the component structure in the updated sub-graph would be identical. Our goal is thus to design a coupling of the activation of the components that activates the same number of vertices in both copies in every step.

In order for the initial two-step coupling to succeed, certain (additional) properties of the configurations are required. These properties are achieved with a continuation of the initial burn-in phase for a small number of $O(\log\omega(n))$ steps. For a random-cluster configuration $X$ , let $\widetilde{\mathcal{R}}_{\omega}(X)=\sum_{j:L_{j}(X)\leq B_{\omega}}L_{j}(X)^{2}$ and let $I(X)$ denote the number of isolated vertices of $X$ . Our extension of the burn-in period is captured by the following lemma.

Lemma 2.6.

Let $\zeta=q$ , $q\in(1,2)$ and suppose $X_{0}$ is such that $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ . Then, there exists $T=O(\log\omega(n))$ and a constant $\beta>0$ such that $\widetilde{\mathcal{R}}_{\omega}(X_{T})=O(n^{4/3}{\omega(n)}^{-1/2})$ , $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ and $I(X_{T})=\Omega(n)$ with probability $\Omega(\omega(n)^{-\beta})$ .

The proof of Lemma 2.6 is provided in Section 5.1.

With these bounds on $\widetilde{\mathcal{R}}_{\omega}(X_{T})$ , $\widetilde{\mathcal{R}}_{\omega}(Y_{T})$ , $I(X_{T})$ and $I(Y_{T})$ , we construct the two-step coupling for matching the large component structure. The construction crucially relies on a new local limit theorem (Theorem 5.1). In particular, under our assumptions, when $\omega(n)$ is small enough, there are few components with sizes above $B_{\omega}$ . Hence, we can condition on the event that all of them are activated simultaneously. The difference in the number of active vertices generated by the activation of these large components can then be “corrected” by a coupling of the activation of the smaller components; for this we use our new local limit theorem.

Specifically, our local limit theorem applies to the random variables corresponding to the number of activated vertices from the small components of each copy. We prove it using a result of Mukhin [28] and the fact that, among the small components, there are (roughly speaking) many components of many different sizes. To establish the latter we require a refinement of known random graph estimates (see Lemma 3.11).

To formally state our result we introduce some additional notation. Let $\mathcal{S}_{\omega}(X)$ be the set of connected components of $X$ with sizes greater than $B_{\omega}$ . At step $t$ , the activation of the components of two random-cluster configurations $X_{t}$ and $Y_{t}$ is done using a maximal matching $W_{t}$ between the components of $X_{t}$ and $Y_{t}$ , with the restriction that only components of equal size are matched to each other. For an increasing positive function $g$ and each integer $k\geq 0$ , define $\hat{N}_{k}(t,g):=\hat{N}_{k}(X_{t},Y_{t},g)$ as the number of matched pairs in $W_{t}$ whose component sizes are in the interval

\mathcal{I}_{k}(g)=\Big{[}\frac{\vartheta n^{2/3}}{2g(n)^{2^{k}}},\frac{\vartheta n^{2/3}}{g(n)^{2^{k}}}\Big{]},

where $\vartheta>0$ is a fixed large constant (independent of $n$ ).

Lemma 2.7.

Let $\zeta=q$ , $q\in(1,2)$ and suppose $X_{0},Y_{0}$ are random-cluster configurations such that $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ , $\widetilde{\mathcal{R}}_{\omega}(X_{0})=O(n^{4/3}{\omega(n)}^{-1/2})$ , $I(X_{0})=\Omega(n)$ and similarly for $Y_{0}$ . Then, there exists a two-step coupling of the CM dynamics such that $\mathcal{S}_{\omega}(X_{2})=\mathcal{S}_{\omega}(Y_{2})$ with probability $\exp\left(-O(\omega(n)^{9})\right)$ .

Moreover, $L_{1}(X_{2})=O(n^{2/3}\omega(n))$ , $\mathcal{R}_{2}(X_{2})=O(n^{4/3})$ , $\widetilde{\mathcal{R}}_{\omega}(X_{2})=O(n^{4/3}{\omega(n)}^{-1/2})$ , $I(X_{2})=\Omega(n)$ , $\hat{N}_{k}(2,\omega(n))=\Omega({\omega(n)}^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k-1}}\rightarrow\infty$ , and similarly for $Y_{2}$ .

From the first part of the lemma we obtain two configurations that agree on all of their large components, as desired, while the second part guarantees additional structural properties for the resulting configurations so that the next sub-phase of the coupling can also succeed with the required probability. The proof of Lemma 2.7 is given in Section 5.2.

In the second sub-phase, after the large component are matched, we can design a coupling that activates exactly the same number of vertices from each copy of the chain. To analyze this coupling we use a precise estimate on the distribution of the maximum of symmetric random walks over integers (with steps of different sizes). We are first required to run the chains coupled for $T=O(\log\omega(n))$ steps, so that certain additional structural properties appear. Let $M(X_{t})$ and $M(Y_{t})$ be the components in the matching $W_{t}$ that belong to $X_{t}$ and $Y_{t}$ , respectively, and let $D(X_{t})$ and $D(Y_{t})$ be the complements of $M(X_{t})$ and $M(Y_{t})$ . Let

Z_{t}=\sum\nolimits_{\mathcal{C}\in D(X_{t})\cup D(Y_{t})}|\mathcal{C}|^{2}.

Lemma 2.8.

Let $\zeta=q$ , $q\in(1,2)$ . Suppose $X_{0}$ and $Y_{0}$ are random-cluster configurations such that $\mathcal{S}_{\omega}(X_{0})=\mathcal{S}_{\omega}(Y_{0})$ , and $\hat{N}_{k}(0,\omega(n))=\Omega({\omega(n)}^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k-1}}\rightarrow\infty$ . Suppose also that $L_{1}(X_{0})=O(n^{2/3}\omega(n))$ , $\mathcal{R}_{2}(X_{0})=O(n^{4/3})$ , $\widetilde{\mathcal{R}}_{\omega}(X_{0})=O(n^{4/3}{\omega(n)}^{-1/2})$ , $I(X_{0})=\Omega(n)$ , and similarly for $Y_{0}$ .

Then, there exists a coupling of the CM steps such that with probability $\exp(-O((\log\omega(n))^{2}))$ after $T=O(\log\omega(n))$ steps: $\mathcal{S}_{\omega}(X_{T})=\mathcal{S}_{\omega}(Y_{T})$ , $Z_{T}=O(n^{4/3}{\omega(n)}^{-1/2})$ , $\hat{N}_{k}(T,\omega(n)^{1/2})=\Omega({\omega(n)}^{3\cdot 2^{k-2}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k-1}}\rightarrow\infty$ , $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ , $I(X_{T})=\Omega(n)$ , and similarly for $Y_{T}$ .

The proof of Lemma 2.8 also uses our local limit theorem (Theorem 5.1) and is provided in Section 5.3.

The final step of our construction is a coupling of the activation of the components of size less than $B_{\omega}$ , so that exactly the same number of vertices are activated from each copy in each step w.h.p.

Lemma 2.9.

Let $\zeta=q$ , $q\in(1,2)$ and suppose $X_{0}$ and $Y_{0}$ are random-cluster configurations such that $\mathcal{S}_{\omega}(X_{0})=\mathcal{S}_{\omega}(Y_{0})$ , $Z_{0}=O(n^{4/3}{\omega(n)}^{-1/2})$ , and $\hat{N}_{k}\left(0,\omega(n)^{1/2}\right)=\Omega({\omega(n)}^{3\cdot 2^{k-2}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k-1}}\rightarrow\infty$ . Suppose also that $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ , $I(X_{0})=\Omega(n)$ and similarly for $Y_{0}$ . Then, there exist a coupling of the CM steps and a constant $\beta>0$ such that after $T=O(\log n)$ steps, $X_{T}$ and $Y_{T}$ have the same component structure with probability $\Omega\left((\log\log\log n)^{-\beta}\right)$ .

We comment briefly on how we prove this lemma. Our starting point is two configurations with the same “large” component structure; i.e., $\mathcal{S}_{\omega}(X_{0})=\mathcal{S}_{\omega}(Y_{0})$ . We use the maximal matching $W_{0}$ to couple the activation of the large components in $X_{0}$ and $Y_{0}$ . The small components not matched by $W_{0}$ , i.e., those counted in $Z_{0}$ , are then activated independently. This creates a discrepancy $\mathcal{D}_{0}$ between the number of active vertices from each copy. Since $\operatorname*{{\rm E}}[\mathcal{D}_{0}]=0$ and $\operatorname*{{\rm Var}}(\mathcal{D}_{0})=\Theta(Z_{0})=\Theta({n^{4/3}}{\omega(n)^{-1/2}})$ , it follows from Hoeffding’s inequality that $\mathcal{D}_{0}\leq{n^{2/3}}{\omega(n)^{-1/4}}$ w.h.p. To fix this discrepancy, we use the small components matched by $W_{0}$ . Specifically, under the assumptions in Lemma 2.9, we can construct a coupling of the activation of the small components so that the difference in the number of activated vertices from the small components from each copy is exactly $\mathcal{D}_{0}$ with probability $\Omega(1)$ . This part of the construction utilizes random walks over the integers; in particular, we use a lower bound for the maximum of such a random walk.

We need to repeat this process until $Z_{t}=0$ ; this takes $O(\log n)$ steps since $Z_{t}\approx(1-1/q)^{t}Z_{0}$ . However, there are a few complications. First, the initial assumptions on the component structure of the configurations are not preserved for this many steps w.h.p., so we need to relax the requirements as the process evolves. This is in turn possible because the discrepancy $\mathcal{D}_{t}$ decreases with each step, which implies that the probability of success of the coupling increases at each step. See Section 5.4 for the detailed proof.

We now indicate how these lemmas lead to a proof of Theorem 2.5 stated earlier.

Proof of Theorem 2.5.

Suppose $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ and $\mathcal{R}_{1}(Y_{0})=O(n^{4/3})$ . It follows from Lemma 2.6, 2.7, 2.8 and 2.9 that there exists a coupling of the CM steps such that after $T=O(\log n)$ steps, $X_{T}$ and $Y_{T}$ could have the same component structure. This coupling succeeds with probability at least

\rho=\Omega(\omega(n)^{-\beta_{1}})\cdot\exp\big{(}-O(\omega(n)^{9})\big{)}\cdot\exp\big{(}-O\big{(}(\log\omega(n))^{2}\big{)}\big{)}\cdot\Omega\big{(}(\log\log\log n)^{-\beta_{2}}\big{)},

where $\beta_{1},\beta_{2}>0$ are constants. Thus, $\rho=\Omega\big{(}(\log\log n)^{-1}\big{)}$ , since $\omega(n)=\log\log\log\log n$ . ∎

Remark 3.

We pause to mention that this delicate coupling for the activation of the components is not required when $\zeta=q$ and $q>2$ . In that regime, the random-cluster model is super-critical, so after the first $O(\log n)$ steps, the component structure is much simpler, with exactly one large component. On the other hand, when $\zeta=q$ and $q\in(1,2]$ the model is critical, which, combined with the fact mentioned earlier that the percolation sub-step of the dynamics is also critical when $\zeta=q$ , makes the analysis of the CM dynamics in this regime quite subtle.

2.3 Coupling to the same configuration

In the last phase of the coupling, suppose we start with two configurations $X_{0}$ , $Y_{0}$ with the same component structure. We are still required to bound the number of steps until the same configuration is reached. The following lemma from [7] supplies the desired bound.

Lemma 2.10 ([7], Lemma 24).

Let $q>1$ , $\zeta>0$ and let $X_{0}$ , $Y_{0}$ be two random-cluster configurations with the same component structure. Then, there exists a coupling of the CM steps such that after $T=O(\log n)$ steps, $X_{T}=Y_{T}$ w.h.p.

Combining the results for each of the phases of the coupling, we now prove Theorem 1.1.

Proof of Theorem 1.1.

By Theorem 2.4, after $t_{0}=O(\log n)$ steps, with probability $\Omega(1)$ , we have $\mathcal{R}_{1}(X_{t_{0}})=O(n^{4/3})$ and $\mathcal{R}_{1}(Y_{t_{0}})=O(n^{4/3})$ . If this is the case, Theorem 2.5 and Lemma 2.10 imply that there exists a coupling of the CM steps such that with probability $\Omega\left((\log\log n)^{-1}\right)$ after an additional $t_{1}=O(\log n)$ steps, $X_{t_{0}+t_{1}}=Y_{t_{0}+t_{1}}$ . Consequently, we obtain that $\tau_{\rm mix}^{\mathrm{CM}}=O(\log n\cdot\log\log n)$ as claimed. ∎

Remark 4.

The probability of success in Theorem 2.5, which governs the lower order term $O(\log\log n)$ in our mixing time bound, is controlled by our choice of the function $\omega(n)$ for the definition of “large components”. By choosing $\omega(n)$ that goes to $\infty$ more slowly, we could improve our mixing time bound to $O(\log n\cdot g(n))$ where $g(n)$ is any function that tends to infinity arbitrarily slowly. However, it seems that new ideas are required to obtain a bound of $O(\log n)$ (matching the known lower bound). In particular, the fact that $\omega(n)\rightarrow\infty$ is crucially used in some of our proofs. Our specific choice of $\omega(n)$ yields the $O(\log n\cdot\log\log n)$ bound and makes our analysis cleaner.

3 Random graph estimates

In this section, we compile a number of standard facts about the $G(n,p)$ random graph model which will be useful in our proofs. We use $G\sim G(n,p)$ to denote a random graph $G$ sampled from the standard $G(n,p)$ model, in which every edge appears independently with probability $p$ . A $G(n,p)$ random graph is said to be sub-critical when $np<1$ . It is called super-critical when $np>1$ and critical when $np=1$ . For a graph $G$ , with a slight abuse of notation, let $L_{i}(G)$ denote the size of the $i$ -th largest connected component in $G$ , and let $\mathcal{R}_{i}(G):=\sum_{j\geq i}L_{j}(G)^{2}$ ; note that the same notation is used for the components of a random-cluster configuration, but it will always be clear from context which case is meant.

Fact 3.1.

Given $0<N_{1}<N_{2}$ and $p\in[0,1]$ . Let $G_{1}\sim G(N_{1},p)$ and $G_{2}\sim G(N_{2},p)$ . For any $K>0$ , $\Pr[L_{1}(G_{1})>K]\leq\Pr[L_{1}(G_{2})>K]$ .

Proof.

Consider the coupling of $(G_{1},G_{2})$ such that $G_{1}$ is a subgraph of $G_{2}$ . $L_{1}(G_{1})\leq L_{1}(G_{2})$ with probability 1. Proposition just follows from Strassen’s theorem (see, e.g., Theorem 22.6 in [22]). ∎

Lemma 3.2 ([24], Lemma 5.7).

Let $I(G)$ denote the number of isolated vertices in $G$ . If $np=O(1)$ , then there exists a constant $C>0$ such that

\Pr[I(G)>Cn]=1-O(n^{-1}).

Consider the equation

e^{-dx}=1-x

(3)

and let $\beta(d)$ be defined as its unique positive root. Observe that $\beta$ is well-defined for $d>1$ .

Lemma 3.3 ([4], Lemma 2.7).

Let $G\sim G(n+m,d_{n}/n)$ random graph where $|m|=o(n)$ and $\lim_{n\rightarrow\infty}d_{n}=d$ . Assume $1<d_{n}=O(1)$ and $d_{n}$ is bounded away from $1$ for all $n\in\mathbb{N}$ . Then, For $A=o(\log n)$ and sufficiently large $n$ , there exists a constant $c>0$ such that

\Pr\left[\lvert L_{1}(G)-\beta(d)n\rvert>\lvert m\rvert+A\sqrt{n}\right]\leq e^{-cA^{2}}.

Lemma 3.4 ([4], Lemma 2.16).

For $np>0$ , we have $\operatorname*{{\rm E}}\left[\mathcal{R}_{2}(G)\right]=O\left(n^{4/3}\right)$ .

Consider the near-critical random graph $G\left(n,\frac{1+\varepsilon}{n}\right)$ with $\varepsilon=\varepsilon(n)=o(1)$ .

Lemma 3.5 ([24], Theorem 5.9).

Assume $\varepsilon^{3}n\geq 1$ , then for any $A$ satisfying $2\leq A\leq\sqrt{\varepsilon^{3}n}/10$ , there exists some constant $c>0$ such that

\Pr\left[\left|L_{1}(G)-2\varepsilon n\right|>A\sqrt{\frac{n}{\varepsilon}}\right]=O\left(e^{-cA^{2}}\right).

Corollary 3.6.

Let $G\sim G\left(n,\frac{1+\varepsilon}{n}\right)$ with $\varepsilon=o(1)$ . For any positive constant $\rho\leq 1/10$ , there exist constants $C\geq 1$ and $c>0$ such that if $\varepsilon^{3}n\geq C$ , then

\Pr\left[\left\lvert L_{1}(G)-2\varepsilon n\right\rvert>\rho\varepsilon n\right]=O(e^{-c\varepsilon^{3}n}).

Lemma 3.7 ([24], Theorem 5.12).

Let $\varepsilon<0$ , then $\operatorname*{{\rm E}}[\mathcal{R}_{1}(G)]=O\left(n/|\varepsilon|\right).$

Lemma 3.8 ([24], Theorem 5.13).

Let $\varepsilon>0$ and $\varepsilon^{3}n\geq 1$ for large $n$ , then $\operatorname*{{\rm E}}[\mathcal{R}_{2}(G)]=O\left(n/\varepsilon\right)$ .

For the next results, suppose that $G\sim G(n,\frac{1+\lambda n^{-1/3}}{n})$ , where $\lambda=\lambda(n)$ may depend on $n$ .

Lemma 3.9.

If $|\lambda|=O(1)$ , then $\operatorname*{{\rm E}}\left[\mathcal{R}_{1}(G)\right]=O\left(n^{4/3}\right)$ .

Proof.

Follows from Lemmas 2.13, 2.15 and 2.16 in [4]. ∎

All the random graph facts stated so far can be either found in the literature, or follow directly from well-known results. The following lemmas are slightly more refined versions of similar results in the literature.

Lemma 3.10.

Suppose $|\lambda|=O(h(n))$ and let $B_{h}={n^{2/3}}{h(n)^{-1}}$ , where $h:\mathbb{N}\rightarrow\mathbb{R}$ is a positive increasing function such that $h(n)=o(\log n)$ . Then, for any $\alpha\in(0,1)$ there exists a constant $C=C(\alpha)>0$ such that, with probability at least $\alpha$ ,

\sum\nolimits_{j:L_{j}(G)\leq B_{h}}L_{j}(G)^{2}\leq C{n^{4/3}}{h(n)^{-1/2}}.

Lemma 3.11.

Let $S_{B}=\{j:B\leq L_{j}(G)\leq 2B\}$ and suppose there exists a positive increasing function $g$ such that $g(n)\rightarrow\infty$ , $g(n)=o(n^{1/3})$ , $|\lambda|\leq g(n)$ and $B\leq\frac{n^{2/3}}{g(n)^{2}}$ . If $B\rightarrow\infty$ , then there exists constants $\delta_{1},\delta_{2}>0$ independent of $n$ such that

\Pr\left[|S_{B}|\leq\frac{\delta_{1}n}{B^{3/2}}\right]\leq\frac{\delta_{2}B^{3/2}}{n}.

The proofs of Lemmas 3.10 and 3.11 are provided in Appendix C. Finally, the following corollary of Lemma 3.11 will also be useful. For a graph $H$ , let ${N}_{k}(H,g)$ be the number of components of $H$ whose sizes are in the interval $\mathcal{I}_{k}(g)$ . We note that with a slight abuse of notation, for a random-cluster configuration $X$ , we also use ${N}_{k}(X,g)$ for the number of connected components of $X$ in $\mathcal{I}_{k}(g)$ .

Corollary 3.12.

Let $m\in(n/2q,n]$ and let $g$ be an increasing positive function that such that $g(n)=o(m^{1/3})$ , $g(n)\rightarrow\infty$ and $|\lambda|\leq g(m)$ . If $H\sim G\big{(}m,\frac{1+\lambda m^{-1/3}}{m}\big{)}$ , there exists a constant $b>0$ such that, with probability at least $1-O\left(g(n)^{-3}\right)$ , $N_{k}(H,g)\geq bg(n)^{3\cdot 2^{k-1}}$ for all $k\geq 1$ such that $n^{2/3}g(n)^{-2^{k}}\rightarrow\infty$ .

4 The burn-in period: proofs

In this section we will provide proofs for Lemma 2.2 and Lemma 2.3.

4.1 A drift function

Consider the mean-field random-cluster model with parameters $q\geq 1$ and $p=\zeta/n$ . In this subsection, we introduce a drift function captures the rate of decay of the size of the largest component in a configuration under steps of the CM dynamics which will be helpful for proving Lemma 2.2; this function was first studied in [7].

Given $\theta\in(0,1]$ , consider the equation

e^{-\zeta x}=1-\frac{qx}{1+(q-1)\theta}

(4)

and let $\phi(\theta,\zeta,q)$ be defined as the largest positive root of (4). We shall see that $\phi$ is not defined for all $q$ and $\zeta$ since there may not be a positive root. When $\zeta$ and $q$ are clear from the context we use $\phi(\theta)=\phi(\theta,\zeta,q)$ . Note that $\beta(\zeta)$ defined by equation (3) is the special case of (4) when $q=1$ ; observe that $\beta$ is only well-defined when $\zeta>1$ .

We let $k(\theta,q):=(1+(q-1)\theta)/q$ so that $\phi(\theta,\zeta,q)=\beta(\zeta\cdot k(\theta,q))\cdot k(\theta,q).$ Hence, $\phi(\theta,\zeta,q)$ is only defined when $\zeta\cdot k(\theta,q)>1$ ; that is, $\theta\in(\theta_{min},1]$ , where $\theta_{min}=\frac{q-\zeta}{\zeta(q-1)}$ . Note that when $\zeta=q$ , $\phi(\theta)$ is defined for every $\theta\in(0,1]$ .

For fixed $\zeta$ and $q$ , we call $f(\theta):=\theta-\phi(\theta)$ the drift function. which is defined on $(\max\{\theta_{min},0\},1]$ .

Lemma 4.1.

When $q=\zeta<2$ , the drift function $f$ is non-negative for any $\theta\in[\xi,1]$ , where $\xi$ is an arbitrarily small positive constant.

Proof.

When $\zeta=q<2$ , the drift function $f$ does not have a positive root, it is continuous in (0,1], and $f(1)>0$ ; see Lemma 2.5 in [9] and Fact 3.5 in [4]. Since $\lim_{\theta\rightarrow 0}f(\theta)=0$ , the result follows. ∎

4.2 Shrinking a large component: proof of Lemma 2.2

The proof of Lemma 2.2 uses the following lemma, which follows directly from standard random graph estimates and Hoeffding’s inequality. To simplify the notation, we let $\hat{L}(X):=L_{1}(X)/n^{2/3}$ . We use $A(X)$ to denote the number of vertices activated by the step CM dynamics from configuration $X$ . Let $\Lambda_{t}$ denote the event that the largest component of the configuration is activated in step $t$ .

Lemma 4.2 ([4], Claim 3.45).

Suppose $\mathcal{R}_{2}(X_{t})=O(n^{4/3})$ and $\hat{L}(X_{t})\geq B$ for a large constant $B$ , and let $C$ be a fixed large constant. Then

1.

$\Pr\left[\mathcal{R}_{2}(X_{t+1})<\mathcal{R}_{2}(X_{t})+\frac{Cn^{4/3}}{\sqrt{\hat{L}(X_{t})}}~{}\middle|~{}X_{t},\Lambda_{t}\right]=1-O\left(\hat{L}(X_{t})^{-1/2}\right)$ .
2.

$\Pr\left[\mathcal{R}_{2}(X_{t+1})<\mathcal{R}_{2}(X_{t})+\frac{Cn^{4/3}}{\sqrt{\hat{L}(X_{t})}}~{}\middle|~{}X_{t},\neg\Lambda_{t}\right]=1-O\left(\hat{L}(X_{t})^{-1/2}\right)$ .

Proof of Lemma 2.2.

Let $\hat{T}$ be the first time $t$ when $\hat{L}(X_{t})\leq\delta n^{1/3}$ , let $T^{\prime}$ be a large constant we choose later; we set $T:=\min\{\hat{T},T^{\prime}\}$ . Observe that with constant probability the largest component in the configuration is activated by the CM dynamics for every $t\leq T^{\prime}$ ; i.e., the event $\Lambda_{t}$ occurs for every $t\leq T^{\prime}$ . Let us assume this is the case and fix $t<T$ . Suppose $\mathcal{R}_{2}(X_{t})\leq\mathcal{R}_{2}(X_{0})+t\cdot\frac{C}{\sqrt{\delta}}n^{\frac{7}{6}}$ where $C$ is the positive constant from Lemma 4.2. We show that with high probability:

(i)

$\mathcal{R}_{2}(X_{t+1})\leq\mathcal{R}_{2}(X_{0})+t\cdot\frac{C}{\sqrt{\delta}}n^{\frac{7}{6}}$ ; and
(ii)

$L_{1}(X_{t+1})\leq L_{1}(X_{t})-\xi n$ where $\xi$ is a positive constant independent of $t$ and $n$ .

In particular, it suffices to set $T^{\prime}=(1-\delta)/\xi$ for the lemma to hold.

First, we show that $A(X_{t})$ is concentrated around its mean. Let $L_{1}(X_{t}):=\theta_{t}n$ and $L_{1}(X_{t+1}):=\theta_{t+1}n$ . Let $\operatorname*{{\rm E}}[A(X_{t})\mid\Lambda_{t}]=\mu_{t}=\frac{n}{q}+(1-\frac{1}{q})\cdot\theta_{t}n$ , $\gamma:=n^{5/6}$ , and $J_{t}:=[\mu_{t}-\gamma,\mu_{t}+\gamma]$ . Hoeffding’s inequality implies

\displaystyle\Pr\left[A(X_{t})\in J_{t}\mid\Lambda_{t}\right]

\displaystyle\geq 1-2\exp\left(\frac{-2\gamma^{2}}{\mathcal{R}_{2}(X_{t})}\right)=1-e^{-\Omega(n^{1/3})}.

If $A(X_{t})\in J_{t}$ , then the random graph $G(A(X_{t}),p)$ is super-critical since

A(X_{t})\cdot p\geq(\mu_{t}-\gamma)\cdot\frac{q}{n}=\left[\frac{n}{q}+\left(1-\frac{1}{q}\right)\cdot\theta_{t}n-n^{5/6}\right]\cdot\frac{q}{n}=1+(q-1)\theta_{t}-o(1)>1.

Next, for a super-critical random graph, Lemma 3.3 provides a concentration bound for the size of largest new component, provided $A(X_{t})\in J_{t}$ . To see this, we write $G(A(X_{t}),\zeta/n)$ as

G\left(\mu_{t}+m,k(\theta_{t},q)\cdot q/\mu_{t}\right),

where $m:=A(X_{t})-\mu_{t}$ ; notice that $|m|\leq\gamma=o(n)$ . Let $H\sim G\left(\mu_{t}+m,k(\theta_{t},q)\cdot q/\mu_{t}\right)$ . Since

k(\theta_{t},q)\cdot q=1+(q-1)\theta_{t}>1+\delta(q-1)>1

holds regardless of $n$ , Lemma 3.3 implies that for $\phi(\theta_{t})>0$ defined in Section 4.1, with high probability

L_{1}(H)\in\left[\phi(\theta_{t})n-\sqrt{n\log n}-|m|,\phi(\theta_{t})n+\sqrt{n\log n}+|m|\right].

Note that $L_{1}(H)=\Omega(n)$ w.h.p.; hence, since $L_{2}(X_{t})=O(n^{2/3})$ we have $L_{1}(X_{t+1})=L_{1}(H)$ w.h.p. We have shown that w.h.p.

\theta_{t+1}-\theta_{t}\leq\phi(\theta_{t})+\frac{\sqrt{n\log n}}{n}-\theta_{t}-\frac{|m|}{n}=-f(\theta_{t})+\sqrt{\frac{\log n}{n}}-\frac{|m|}{n},

where $f$ is the drift function defined in Section 4.1. By Lemma 4.1, we know $f(\theta_{t})>\xi_{1}>0$ for sufficiently small constant $\xi_{1}$ (independent of $n$ and $t$ ). Hence, w.h.p. for sufficiently large $n$

L_{1}(X_{t+1})-L_{1}(X_{t})\leq-\xi_{1}n+o(n)\leq\frac{-\xi_{1}n}{2};

this establishes (ii) from above.

For (i), note that for $t<T$ we have $\hat{L}(X_{t})>\delta n^{1/3}$ , so Lemma 4.2 implies,

\Pr\left[\mathcal{R}_{2}(X_{t+1})<\mathcal{R}_{2}(X_{0})+t\cdot\frac{C}{\sqrt{\delta}}n^{\frac{7}{6}}+\frac{Cn^{4/3}}{\sqrt{\delta}n^{1/6}}\right]=1-o(1).

A union bound implies that these two events occur simultaneously w.h.p. and the result follows. ∎

4.3 Shrinking a medium size component: proof of Lemma 2.3

In the third sub-phase of the burn-in period, we show that ${L_{1}}(X_{t})$ contracts at a constant rate; the precise description of this phenomenon is captured in the following lemma.

Lemma 4.3.

Suppose $\mathcal{R}_{2}(X_{t})=O(n^{4/3})$ , $\delta n^{1/3}\geq\hat{L}(X_{t})\geq B$ for a large constant $B:=B(q)$ , and a small constant $\delta(q,B)$ . Then:

There exists a constant $\alpha:=\alpha(B,q,\delta)<1$ such that

\Pr\left[L_{1}(X_{t+1})\leq\max\{\alpha L_{1}(X_{t}),L_{2}(X_{t})\}\mid X_{t},\Lambda_{t}\right]\geq 1-\exp\left(-\Omega\left(\hat{L}(X_{t})\right)\right);

2.

$\Pr\left[L_{1}(X_{t+1})=L_{1}(X_{t})|X_{t},\neg\Lambda_{t}\right]\geq 1-O\left(\hat{L}(X_{t})^{-3}\right).$

Since Lemmas 4.2 suggests $\mathcal{R}_{2}(X_{t})=O(n^{4/3})$ with reasonably high probability throughout the execution of the sub-phase, Lemmas 4.3 and 4.2 can be combined to derive the following more accurate contraction estimate which will be crucial in the proof Lemma 2.3.

Lemma 4.4.

Suppose $g(n)$ is an arbitrary function with range in the interval $\left[B^{6},\delta n^{1/3}\right]$ where $B$ is a large enough constant such that for $x\geq B^{6}$ we have $x\geq B(\log x)^{8}$ , and $\delta:=\delta(q,B)$ is a small constant.

Suppose $X_{0}$ is such that $g(n)\geq\hat{L}(X_{0})\geq B(\log g(n))^{8}$ and $\mathcal{R}_{2}(X_{0})=O(n^{4/3})$ , then there exists a constant $D$ and $T=O(\log g(n))$ such that at time $T$ , $\hat{L}(X_{T})\leq\max\{B(\log g(n))^{8},D\}$ and $\mathcal{R}_{2}(X_{T})\leq\mathcal{R}_{2}(X_{0})+O\left(\frac{n^{4/3}}{\log g(n)}\right)$ with probability at least $1-O\left(\log^{-1}g(n)\right)$ .

We first provide a proof for Lemma 2.3 that recursively uses the contraction estimate of Lemma 4.4.

Proof of Lemma 2.3.

Let $B$ be a constant large enough so that $\forall x\geq B^{6}$ , we have $x\geq(\log x)^{48}$ . Suppose $\hat{L}(X_{0})\leq\delta n^{1/3}$ and $\mathcal{R}_{2}(X_{0})=O(n^{4/3})$ for the constant $\delta=\delta(q,B)$ from Lemma 4.4. Suppose also $\hat{L}(X_{0})\geq B^{6}$ ; otherwise there is nothing to prove.

Let $g_{0}(n):=\delta n^{1/3}$ and $g_{i+1}(n):=B(\log g_{i}(n))^{8}$ for all $i\geq 0$ . Let $K$ be defined as the minimum natural number such that $g_{K}(n)\leq B^{6}$ . Note that $K=O(\log^{*}n)$ . Assume at time $t\geq 0$ , there exists an integer $j\geq 0$ such that $X_{t}$ satisfies:

1.

$g_{j+1}(n)\leq\hat{L}(X_{t})\leq g_{j}(n)$ , and
2.

$\mathcal{R}_{2}(X_{t})=O(n^{4/3})+O\left(\sum_{k=0}^{j-1}\frac{n^{4/3}}{\log g_{k}(n)}\right)$ .

We show there exists time $t^{\prime}>t$ such that properties 1 and 2 hold for $X_{t^{\prime}}$ for a different index $j^{\prime}>j$ . The following bounds on sums and products involving the $g_{i}$ ’s will be useful; the proof is elementary and delayed to the end of this section.

Claim 4.5.

Let $K$ be defined as above. $\forall j<K,$

(i)

For any positive constant $c$ , we have $\prod_{i=0}^{j}\left(1-\frac{c}{\log g_{i}(n)}\right)\geq 1-\frac{1.5c}{\log g_{j}(n)}$
(ii)

$\sum_{i=0}^{j}\frac{1}{\log g_{i}(n)}\leq\frac{1.5}{\log g_{j}(n)}$

By part (ii) of this claim, note that

O\left(\sum_{k=0}^{j-1}\frac{n^{4/3}}{\log g_{k}(n)}\right)=O\left(\frac{n^{4/3}}{\log g_{j-1}(n)}\right)=O(n^{4/3}).

Hence, Lemma 4.4 implies that with probability $1-O\left((\log g_{j}(n))^{-1}\right)$ there exist a time $t^{\prime}\leq t+O(\log g_{j}(n))$ and a large constant $D$ such that $\hat{L}(X_{t^{\prime}})\leq\max\{B(\log g_{j}(n))^{8},D\}$ and $\mathcal{R}_{2}(X_{t^{\prime}})\leq\mathcal{R}_{2}(X_{t})+O\left(\frac{n^{4/3}}{\log g_{j}(n)}\right).$ If $\hat{L}(X_{t^{\prime}})\leq\max\{D,B^{6}\}$ we are done. Hence, suppose otherwise that $\hat{L}(X_{t^{\prime}})\in(B^{6},\log g_{j+1}(n)]$ . Since the interval $(B^{6},\log g_{j+1}(n)]$ is completely covered by the union of the intervals $[g_{j+2},g_{j+1}]$ , …, $[g_{K},g_{K-1}]$ , there must be an integer $j^{\prime}\geq j+1$ such that $g_{j^{\prime}+1}(n)\leq\hat{L}(X_{t^{\prime}})\leq g_{j^{\prime}}(n)$ . Also, notice

	$\displaystyle\mathcal{R}_{2}(X_{t^{\prime}})$	$\displaystyle\leq\mathcal{R}_{2}(X_{t})+O\left(\frac{n^{4/3}}{\log g_{j}(n)}\right)=O(n^{4/3})+O\left(\sum_{k=0}^{j-1}\frac{n^{4/3}}{\log g_{k}(n)}\right)+O\left(\frac{n^{4/3}}{\log g_{j}(n)}\right)$
		$\displaystyle=O(n^{4/3})+O\left(\sum_{k=0}^{j}\frac{n^{4/3}}{\log g_{k}(n)}\right)=O(n^{4/3})+O\left(\sum_{k=0}^{j^{\prime}-1}\frac{n^{4/3}}{\log g_{k}(n)}\right).$

By taking at most $K$ steps of induction, we obtain that there exist constants $C$ and $c$ such that with probability at least $\rho:=\prod_{i=0}^{K-1}\left(1-\frac{c}{\log g_{i}(n)}\right),$ there exists a time

t_{K}\leq\sum_{i=0}^{K-1}C\log g_{i}(n)

that satisfies $\hat{L}(X_{t_{K}})\leq g_{K}(n)\leq B^{6}$ and $\mathcal{R}_{2}(X_{t_{K}})=O(n^{4/3})$ . Observe that $t_{K}$ is a time when our goal has been achieved, so it only remains to show that $\rho=\Omega(1)$ and $t_{K}=O(\log n)$ . The lower bound on $\rho$ follows from part (i) of Claim 4.5:

\displaystyle\prod_{i=0}^{K-1}1-\frac{c}{\log g_{i}(n)}

\displaystyle\geq 1-\frac{1.5c}{\log g_{K-1}(n)}>1-\frac{1.5c}{\log B^{6}}=\Omega(1).

By noting that $K=O(\log^{*}n)$ , we can also bound $t_{K}$ since $\sum_{i=0}^{K-1}C\log g_{i}(n)$ is at most $\log g_{0}(n)+(K-1)\log g_{1}(n)=O(\log n)$ . ∎

Before proving Lemma 4.4 we provide the proof of Lemma 4.3.

Proof of Lemma 4.3.

We start with part 1. Let $\mu_{t}:=\operatorname*{{\rm E}}[A(X_{t})|\Lambda_{t},X_{t}]$ , $\gamma_{t}:=\sqrt{\hat{L}(X_{t})}\cdot n^{2/3}$ , and $J_{t}:=[\mu_{t}-\gamma_{t},\mu_{t}+\gamma_{t}]$ . Hoeffding’s inequality implies that

\begin{split}\Pr\left[A(X_{t})\in J_{t}\mid\Lambda_{t},X_{t}\right]&\geq 1-2\exp\left(\frac{-2\gamma_{t}^{2}}{\mathcal{R}_{2}(X_{t})}\right)=1-\exp\left(-\Omega(\hat{L}(X_{t}))\right).\end{split}

Let $m:=\mu_{t}+\gamma_{t}$ , $G\sim G(m,\frac{q}{n})$ and $\hat{G}\sim G(A(X_{t}),p)$ . Then, the monotonicity of the largest component in a random graph implies that for any $\ell>0$

	$\displaystyle\Pr\left[L_{1}(\hat{G})>\ell\mid A(X_{t})\in J_{t}\right]$
	$\displaystyle=\sum_{a\in J_{t}}\Pr\left[L_{1}(\hat{G})>\ell\mid A(X_{t})=a\right]\Pr\left[A(X_{t})=a\mid A(X_{t})\in J_{t}\right]$
	$\displaystyle\leq\sum_{a\in J_{t}}\Pr\left[L_{1}(\hat{G})>\ell\mid A(X_{t})=m\right]\Pr\left[A(X_{t})=a\mid A(X_{t})\in J_{t}\right]$
	$\displaystyle=\Pr[L_{1}(G)>\ell]\sum_{a\in J_{t}}\Pr[A(X_{t})=a\mid A(X_{t})\in J_{t}]$
	$\displaystyle=\Pr[L_{1}(G)>\ell].$

We bound next $\Pr[L_{1}(G)>\ell]$ . For this, we rewrite $G(m,\frac{q}{n})$ as $G\left(m,\frac{1+\varepsilon}{m}\right)$ ; since

\mu_{t}=\hat{L}(X_{t})\cdot n^{2/3}+\left(n-\hat{L}(X_{t})n^{2/3}\right)q^{-1}

we have

\varepsilon=m\cdot\frac{q}{n}-1=\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)\frac{\hat{L}(X_{t})}{n^{1/3}}.

Thus,

	$\displaystyle\varepsilon^{3}\cdot m$	$\displaystyle=\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)^{3}\frac{\hat{L}(X_{t})^{3}}{n}\left(\hat{L}(X_{t})n^{2/3}+\frac{n-\hat{L}(X_{t})n^{2/3}}{q}+\sqrt{\hat{L}(X_{t})}n^{2/3}\right)$
		$\displaystyle\geq\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)^{3}\cdot\frac{\hat{L}(X_{t})^{3}}{n}\cdot\frac{n}{q}$
		$\displaystyle\geq\frac{1}{q}\cdot\left((q-1)^{3}\hat{L}(X_{t})^{3}+q^{3}\sqrt{\hat{L}(X_{t})}^{3}\right)$
		$\displaystyle\geq q^{2}\hat{L}(X_{t})^{3/2}\geq 100\hat{L}(X_{t}),$

where the last inequality follows from the fact that $\hat{L}(X_{t})>B$ , where $B=B(q)$ is a sufficiently large constant.

Since $\varepsilon^{3}\cdot m\geq 1$ , Lemma 3.5 implies

\Pr\left[\lvert L_{1}(G)-2\varepsilon m\rvert>\sqrt{\hat{L}(X_{t})}\sqrt{\frac{m}{\varepsilon}}\right]=e^{-\Omega\left(\hat{L}(X_{t})\right)}.

Let $c_{1}=2\sqrt{\frac{1+(q-1)\delta}{q(q-1)}}$ . The upper tail bound implies

\Pr\left[L_{1}(G)\leq 2\varepsilon m+c_{1}n^{2/3}\right]\geq 1-e^{-\Omega\left(\hat{L}(X_{t})\right)}.

We show next that $2\varepsilon m+c_{1}n^{2/3}\leq\alpha L_{1}(X_{t})$ for some $\alpha\in(0,1)$ .

		$\displaystyle 2\varepsilon m+c_{1}n^{2/3}$
	$\displaystyle=$	$\displaystyle 2\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)\frac{\hat{L}(X_{t})}{n^{1/3}}\left(\hat{L}(X_{t})n^{2/3}+\frac{n-\hat{L}(X_{t})n^{2/3}}{q}+\sqrt{\hat{L}(X_{t})}n^{2/3}\right)+c_{1}n^{2/3}$
	$\displaystyle=$	$\displaystyle\frac{2}{q}\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)\frac{\hat{L}(X_{t})}{n^{1/3}}\left[n+\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)\hat{L}(X_{t})n^{2/3}\right]+c_{1}n^{2/3}$
	$\displaystyle=$	$\displaystyle\frac{2}{q}\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}+\frac{c_{1}q}{\hat{L}(X_{t})}\right)\hat{L}(X_{t})n^{2/3}+\frac{2}{q}\left(q-1+\frac{q}{\sqrt{\hat{L}(X_{t})}}\right)^{2}\hat{L}(X_{t})^{2}n^{1/3}$
	$\displaystyle\leq$	$\displaystyle\frac{2}{q}\left[\delta\left(q-1+O\left(\hat{L}(X_{t})^{-1/2}\right)\right)^{2}+\left(q-1+O\left(\hat{L}(X_{t})^{-1/2}\right)\right)\right]\hat{L}(X_{t})n^{2/3},$

where in the last inequality we use the assumption that $\delta n^{1/3}\geq\hat{L}(X_{t})$ . For sufficiently small $\delta$ and sufficiently large $B$ , $\exists~{}\alpha<1$ such that

\alpha>\frac{2}{q}\left[\delta\left(q-1+\frac{2q}{B^{1/2}}\right)^{2}+\left(q-1+\frac{2q}{B^{1/2}}\right)\right].

Consequently, $L_{1}\left(G\right)\leq 2\varepsilon m+c_{1}n^{2/3}\leq\alpha L_{1}(X_{t})$ with probability $1-\exp\left(-\Omega(\hat{L}(X_{t})\right)$ . If that is the case, $L_{1}(X_{t+1})\leq\max\left\{\alpha L_{1}(X_{t}),L_{2}(X_{t})\right\}=:L^{+}$ . Therefore,

	$\displaystyle\Pr\left[L_{1}(X_{t+1})\leq L^{+}\mid X_{t},\Lambda_{t}\right]$
	$\displaystyle\geq\Pr\left[L_{1}(X_{t+1})\leq L^{+}\mid X_{t},\Lambda_{t},A(X_{t})\in J_{t}\right]\cdot\Pr\left[A(X_{t})\in J_{t}\mid X_{t},\Lambda_{t}\right]$
	$\displaystyle\geq 1-\exp\left(-\Omega(\hat{L}(X_{t}))\right),$

which concludes the proof of part 1.

For part 2, note first that when the largest component is inactive, we have $L_{1}(X_{t+1})\geq L_{1}(X_{t})$ ; hence, it is sufficient to show that $L_{1}(X_{t+1})\leq L_{1}(X_{t})$ with the desired probability.

Let $\mu_{t}^{\prime}:=\operatorname*{{\rm E}}\left[A(X_{t})\mid\neg\Lambda_{t},X_{t}\right]=\left(n-\hat{L}(X_{t})n^{2/3}\right)q^{-1}$ , $\gamma_{t}^{\prime}:=\sqrt{\hat{L}(X_{t})}\cdot n^{2/3}$ , and $J_{t}^{\prime}:=[\mu_{t}^{\prime}-\gamma_{t}^{\prime},\mu_{t}^{\prime}+\gamma_{t}^{\prime}]$ . By Hoeffding’s inequality,

\Pr\left[A(X_{t})\in J_{t}^{\prime}\mid\neg\Lambda_{t},X_{t}\right]\geq 1-\exp\left(-\Omega\left(\hat{L}(X_{t})\right)\right).

Let $G\sim G(A(X_{t}),p)$ , $m=\mu_{t}^{\prime}+\gamma_{t}^{\prime}$ and let $G^{+}\sim G\left(\mu_{t}^{\prime}+\gamma_{t}^{\prime},p\right)$ , By monotonicity of the largest component in a random graph,

\Pr\left[L_{1}(G)>L_{1}(X_{t})\mid A(X_{t})\in J_{t}^{\prime}\right]\leq\Pr\left[L_{1}(G^{+})>L_{1}(X_{t})\right].

Rewrite $G\left(\mu_{t}^{\prime}+\gamma_{t}^{\prime},p\right)$ as $G\left(m,\frac{1+\varepsilon}{m}\right)$ , where

\varepsilon=\left(\frac{n-\hat{L}(X_{t})n^{2/3}}{q}+\sqrt{\hat{L}(X_{t})}n^{2/3}\right)\cdot\frac{q}{n}-1=\left(\sqrt{\hat{L}(X_{t})}q-\hat{L}(X_{t})\right)n^{-1/3}.

From this bound, applying Lemma 3.7 to $G^{+}$ , we obtain

\operatorname*{{\rm E}}\left[\mathcal{R}_{1}(G^{+})\right]=O\left(\frac{m}{\varepsilon}\right)=O\left(\frac{n^{4/3}}{\hat{L}(X_{t})}\right).

Hence, $\operatorname*{{\rm E}}\left[L_{1}(G^{+})^{2}\right]=O\left(n^{4/3}/\hat{L}(X_{t})\right)$ and by Markov’s inequality

\Pr\left[L_{1}(G^{+})>\hat{L}(X_{t})n^{2/3}\right]=\Pr\left[L_{1}(G^{+})^{2}>\hat{L}(X_{t})^{2}n^{4/3}\right]\leq\frac{\operatorname*{{\rm E}}[L_{1}(G^{+})^{2}]}{\hat{L}(X_{t})^{2}n^{4/3}}=O\left(\frac{1}{\hat{L}(X_{t})^{3}}\right).

To conclude, we observe that

	$\displaystyle\Pr[L_{1}(X_{t+1})\leq L_{1}(X_{t})\mid X_{t},\neg\Lambda_{t}]$
	$\displaystyle\geq\Pr\left[L_{1}(G)\leq L_{1}(X_{t})\mid X_{t},\neg\Lambda_{t},A(X_{t})\in J_{t}^{\prime}\right]\Pr\left[A(X_{t})\in J_{t}^{\prime}\mid X_{t},\neg\Lambda_{t}\right]$
	$\displaystyle\geq\left(1-e^{-\Omega\left(\hat{L}(X_{t})\right)}\right)\left(1-O\left(\frac{1}{\hat{L}(X_{t})^{3}}\right)\right)=1-O\left(\frac{1}{\hat{L}(X_{t})^{3}}\right),$

as desired. ∎

We are now ready to prove Lemma 4.4.

Proof of Lemma 4.4.

Suppose $\mathcal{R}_{2}(X_{0})\leq D_{1}^{2}n^{4/3}$ for a constant $D_{1}$ . Let $T^{\prime}:=B^{\prime}\log g(n)$ , where $B^{\prime}$ is a constant such that $B^{\prime}\log g(n)=2q\log_{1/\alpha}\left(\frac{g(n)}{B(\log g(n))^{8}}\right)$ and $\alpha:=\alpha(B,q,\delta)$ is the constant from Lemma 4.3. Let $\hat{T}$ be the first time

\hat{L}(X_{t})\leq\max\{B(\log g(n))^{8},D\},

where $D$ is a large constant we choose later. Let $T:=T^{\prime}\wedge\hat{T}$ , where the operator $\wedge$ takes the minimum of the two numbers. Define $e(t)$ as the number of steps up to time $t$ in which the largest component of the configuration is activated.

To facilitate the notation, we define the following events. (The constants $C$ and $\alpha$ are those from Lemmas 4.3 and 4.2, respectively).

1.

Let $H_{i}$ denote $\hat{L}(X_{i})>\max\{B(\log g(n))^{8},D\}$ ;
2.

Let $F_{i}$ denote $\mathcal{R}_{2}(X_{i})\leq\mathcal{R}_{2}(X_{i-1})+Cn^{4/3}\hat{L}(X_{i-1})^{-1/2}$ ; let us assume $F_{0}$ occurs;
3.

Let $F^{\prime}_{i}$ denote $\mathcal{R}_{2}(X_{i})\leq\mathcal{R}_{2}(X_{i-1})+Cn^{4/3}(\log g(n))^{-4}B^{-1/2}$ ; again, we assume $F^{\prime}_{0}$ occurs;
4.

Let $Q_{i}$ denote $\hat{L}(X_{i})\leq\max\{\alpha^{e(i)}\hat{L}(X_{0}),D\}$ ;
5.

Let $Base_{i}$ be the intersection of $\{F^{\prime}_{0},Q_{0},H_{0}\},...,\{F^{\prime}_{i-1},Q_{i-1},H_{i-1}\},$ and $\{F^{\prime}_{i},Q_{i}$ }.

By induction, we find a lower bound for the probability of $Base_{T}$ . For the base case, note that $\Pr[Base_{0}]$ $=1$ by assumption. Next we show

\Pr\left[Base_{i+1\wedge T}\mid Base_{i\wedge T}\right]=1-O((\log g(n))^{-4}).

If $T\leq i$ , then $Base_{i\wedge T}=Base_{T}=Base_{i+1\wedge T}$ , so the induction holds. If $T>i$ , then we have $H_{i}$ . By the induction hypothesis $F^{\prime}_{1},F^{\prime}_{2},...,F^{\prime}_{i-1}$ ,

\mathcal{R}_{2}(X_{i})\leq\mathcal{R}_{2}(X_{0})+i\cdot Cn^{4/3}(\log g(n))^{-4}B^{-1/2}.

Moreover, since $i<T\leq T^{\prime}=B^{\prime}\log g(n)$ and $\mathcal{R}_{2}(X_{0})\leq D_{1}^{2}n^{4/3}$ , we have

\mathcal{R}_{2}(X_{i})\leq D_{1}^{2}n^{4/3}+CB^{\prime}n^{4/3}(\log g(n))^{-3}B^{-1/2}.

Given $\mathcal{R}_{2}(X_{i})=O(n^{4/3})$ and $H_{i}$ , Lemma 4.2 implies that $F_{i+1}$ occurs with probability

1-O(\hat{L}(X_{i})^{-1/2})=1-O((\log g(n))^{-4}).

In addition, note that $F_{i+1}\cup H_{i}$ leads to $F^{\prime}_{i+1}$ . Let $\mathbbm{1}(\Lambda_{t})$ be the indicator function for the event $\Lambda_{t}$ . Given $H_{i},Q_{i}$ and $\mathcal{R}_{2}(X_{i})=O(n^{4/3})$ , Lemma 4.3 implies

L_{1}(X_{i+1})\leq\max\{\alpha^{\mathbbm{1}(\Lambda_{t})}L_{1}(X_{i}),L_{2}(X_{i})\}

(5)

with probability at least $1-O\left(\hat{L}(X_{t})^{-3}\right)=1-O\left((\log g(n))^{-24}\right)$ .

Dividing equation (5) by $n^{2/3}$ , we obtain $Q_{i+1}$ for large enough $D$ . In particular, we can choose $D$ to be $D_{1}+2$ . A union bound then implies

\Pr[Base_{i+1\wedge T}\mid Base_{i\wedge T}]\geq\Pr\left[Base_{i+1\wedge T}\mid Base_{i},H_{i}\right]=1-O((\log g(n))^{-4}).

The probability for $Base_{T}$ can then be bounded as follows:

\Pr[Base_{T}]\geq\prod_{i=0}^{T-1}\Pr[Base_{i+1\wedge T}\mid Base_{i\wedge T}]=\prod_{i=0}^{T-1}1-O((\log g(n))^{-4})=1-O((\log g(n))^{-3}).

Next, let us assume $Base_{T}$ . Then we have

\mathcal{R}_{2}(X_{T})\leq\mathcal{R}_{2}(X_{0})+T^{\prime}\cdot Cn^{4/3}(\log g(n))^{-4}B^{-1/2}=\mathcal{R}_{2}(X_{0})+O\left(n^{4/3}(\log g(n))^{-3}\right).

Notice that if $T=\hat{T}$ then the proof is complete. Consequently, it suffices to show $\hat{T}\leq T^{\prime}$ with probability at least $1-g(n)^{-\Omega(1)}$ .

Observe that $K:=e(T^{\prime})$ is a binomial random variable $Bin\left(T^{\prime},1/q\right)$ , whose expectation is $\frac{T^{\prime}}{q}=\frac{B^{\prime}}{q}\log g(n)$ . By Chernoff bound

\Pr\left[K<\frac{B^{\prime}}{2q}\log g(n)\right]\leq\exp\left(-\frac{B^{\prime}}{16q}\log g(n)\right)=g(n)^{-\Omega(1)}.

If indeed $T=T^{\prime}$ and $K\geq\frac{B^{\prime}}{2q}\log g(n)$ , then the event $Q_{T}$ implies

\hat{L}(X_{T})<\alpha^{e(T)}\hat{L}(X_{0})\leq\alpha^{\log_{\alpha}\left(\frac{B(\log g(n))^{8}}{g(n)}\right)}\hat{L}(X_{0})=\frac{B(\log g(n))^{8}}{g(n)}\hat{L}(X_{0})\leq B(\log g(n))^{8},

which leads to $\hat{T}\leq T$ . Therefore,

\Pr\left[\hat{T}>T^{\prime}\mid Base_{T}\right]\leq\Pr\left[K<\frac{B^{\prime}}{2q}\log g(n)\right]=g(n)^{-\Omega(1)},

as desired. ∎

Proof of Claim 4.5.

We first show the following inequality:

\frac{1.5}{\log g_{j}(n)}+\frac{1}{\log g_{j+1}(n)}\leq\frac{1.5}{\log g_{j+1}(n)}.

(6)

Note that by direction computation

\begin{split}\frac{1.5}{\log g_{j}(n)}+\frac{1}{\log g_{j+1}(n)}&=\frac{1.5(\log B+\log(\log g_{j}(n))^{8})+\log g_{j}(n)}{\log g_{j}(n)\log g_{j+1}(n)}.\\ \end{split}

From the definition of $K$ , we know that $g_{j}(n)>B^{6}$ for all $j<K$ . Hence, $\log B<\log g_{j}(n)^{1/6}$ . In addition, recall that $B$ is such that $\forall\,x\geq B^{6}$ , we have $x\geq(\log x)^{48}$ ; therefore, $g_{j}(n)\geq(\log g_{j}(n))^{48}$ . Then, $\log(\log g_{j}(n))^{8}\leq\log g_{j}(n)^{1/6}$ . Putting all these together,

\begin{split}\frac{1.5(\log B+\log(\log g_{j}(n))^{8})+\log g_{j}(n)}{\log g_{j}(n)\log g_{j+1}(n)}&\leq\frac{1.5(\frac{1}{6}\log g_{j}(n)+\frac{1}{6}\log g_{j}(n))+\log g_{j}(n)}{\log g_{j}(n)\log g_{j+1}(n)}\\ &=\frac{1.5\log g_{j}(n)}{\log g_{j}(n)\log g_{j+1}(n)}=\frac{1.5}{\log g_{j+1}(n)}\end{split}

The proof of part (i) is inductive. The base case ( $i=0$ ) holds trivially. For the inductive step note that

\begin{split}\prod_{i=0}^{j+1}\left(1-\frac{c}{\log g_{i}(n)}\right)&=\left(1-\frac{c}{\log g_{j+1}(n)}\right)\prod_{i=0}^{j}\left(1-\frac{c}{\log g_{i}(n)}\right)\\ &\geq\left(1-\frac{c}{\log g_{j+1}(n)}\right)\left(1-\frac{1.5c}{\log g_{j}(n)}\right)\\ &\geq 1-c\left(\frac{1.5}{\log g_{j}(n)}+\frac{1}{\log g_{j+1}(n)}\right)\\ &\geq 1-\frac{1.5c}{\log g_{j+1}(n)},\end{split}

where the last inequality follows from (6).

For part (ii) we also use induction. The base case ( $i=0$ ) can be checked straightforwardly. For the inductive step,

\begin{split}\sum_{i=0}^{j+1}\frac{1}{\log g_{i}(n)}&\leq\frac{1}{\log g_{j+1}(n)}+\sum_{i=0}^{j}\frac{1}{\log g_{i}(n)}\leq\frac{1}{\log g_{j+1}(n)}+\frac{1.5}{\log g_{j}(n)}\leq\frac{1.5}{\log g_{i}(n)},\end{split}

where the last inequality follows from (6). ∎

5 Coupling to the same component structure: proofs

In this section we provide the proofs of Lemma 2.6, Lemma 2.7, Lemma 2.8 and Lemma 2.9.

5.1 Continuation of the burn-in phase: proof of Lemma 2.6

Recall that for a random-cluster configuration $X$ , let $A(X)$ denote the random variable corresponding to the number of vertices activated by step (i) of the CM dynamics from $X$ .

Proof of Lemma 2.6.

We show that there exist suitable constants $C$ , $D>0$ and $\alpha\in(0,1)$ such that if $\mathcal{R}_{1}(X_{t})\leq Cn^{4/3}$ and $\widetilde{\mathcal{R}}_{\omega}(X_{t})>Dn^{4/3}\omega(n)^{-1/2}$ , then

	$\displaystyle\mathcal{R}_{1}(X_{t+1})$	$\displaystyle\leq Cn^{4/3},~{}\text{and}$		(7)
	$\displaystyle\widetilde{\mathcal{R}}_{\omega}(X_{t+1})$	$\displaystyle\leq(1-\alpha)\widetilde{\mathcal{R}}_{\omega}(X_{t})$		(8)

with probability $\rho=\Omega(1)$ . This implies that we can maintain (7)-(8) for $T$ steps with probability $\rho^{T}$ . Precisely, if we let

	$\displaystyle\tau_{1}$	$\displaystyle=\min\{t>0:\mathcal{R}_{1}(X_{t})>Cn^{4/3}\},$
	$\displaystyle\tau_{2}$	$\displaystyle=\min\{t>0:\widetilde{\mathcal{R}}_{\omega}(X_{t})>(1-\alpha)\widetilde{\mathcal{R}}_{\omega}(X_{t-1})\},$
	$\displaystyle T$	$\displaystyle=\min\{\tau_{1},\tau_{2},c\log\omega(n)\},$

where the constant $c>0$ is chosen such that $(1-\alpha)^{c\log\omega(n)}=O(\omega(n)^{-1/2})$ , then $T=c\log\omega(n)$ with probability $\rho^{c\log\omega(n)}$ . (Note that $\rho^{c\log\omega(n)}={\omega(n)}^{-\beta}$ for a suitable constant $\beta>0$ .) Hence, $\mathcal{R}_{1}(X_{T})=O(n^{4/3})$ and

\widetilde{\mathcal{R}}_{\omega}(X_{T})\leq\widetilde{\mathcal{R}}_{\omega}(X_{0})\cdot O(\omega(n)^{-1/2})\leq\mathcal{R}_{1}(X_{0})\cdot O(\omega(n)^{-1/2})=O(n^{4/3}\omega(n)^{-1/2}).

The lemma then follows from the fact that $I(X_{T})=\Omega(n)$ with probability $1-o(1)$ by Lemma 3.2 and a union bound.

To establish (7)-(8), let $\mathcal{H}^{1}_{t}$ be the event that $A(X_{t})\in\left[n/q-\delta n^{2/3},n/q+\delta n^{2/3}\right]$ , where $\delta>0$ is a constant. By Hoeffding’s inequality, for a suitable $\delta>0$ , $\Pr[\mathcal{H}^{1}_{t}]\geq 1-\frac{1}{8q^{2}}$ since $\mathcal{R}_{1}(X_{t})=O(n^{4/3})$ . Let $K_{t}$ denote the subgraph induced on the inactivated vertices at the step $t$ . Observe that $\operatorname*{{\rm E}}\big{[}\widetilde{\mathcal{R}}_{\omega}(K_{t})\big{]}=\left(1-\frac{1}{q}\right)\widetilde{\mathcal{R}}_{\omega}(X_{t})$ . Similarly, $\operatorname*{{\rm E}}\big{[}\mathcal{R}_{1}(K_{t})-\widetilde{\mathcal{R}}_{\omega}(K_{t})\big{]}=\left(1-\frac{1}{q}\right)\big{(}\mathcal{R}_{1}(X_{t})-\widetilde{\mathcal{R}}_{\omega}(X_{t+1})\big{)}$ . Hence, by Markov’s inequality and independence between activation of each component, with probability at least $1/4q^{2}$ , the activation sub-step is such that $G_{u}$ satisfies

\widetilde{\mathcal{R}}_{\omega}(K_{t})\leq\left(1-\frac{1}{2q}\right)\widetilde{\mathcal{R}}_{\omega}(X_{t}),

and

\mathcal{R}_{1}(K_{t})-\widetilde{\mathcal{R}}_{\omega}(K_{t})\leq\left(1-\frac{1}{2q}\right)\big{(}\mathcal{R}_{1}(X_{t})-\widetilde{\mathcal{R}}_{\omega}(X_{t+1})\big{)}.

We denote this event by $\mathcal{H}^{2}_{t}$ . It follows by a union bound that $\mathcal{H}^{1}_{t}$ and $\mathcal{H}^{2}_{t}$ happen simultaneously with probability at least $1/8q^{2}$ . We assume that this is indeed the case and proceed to discuss the percolation sub-step.

Lemma 3.10 implies that there exists $C_{1}>0$ such that with probability $99/100$ ,

\widetilde{\mathcal{R}}_{\omega}\left(G\left(A(X_{t}),\frac{q}{n}\right)\right)\leq C_{1}\frac{n^{4/3}}{{\omega(n)}^{1/2}}.

Hence,

\displaystyle\widetilde{\mathcal{R}}_{\omega}(X_{t+1})=\widetilde{\mathcal{R}}_{\omega}(K_{t})+\widetilde{\mathcal{R}}_{\omega}\left(G\left(A(X_{t}),\frac{q}{n}\right)\right)\leq\left(1-\frac{1}{2q}\right)\widetilde{\mathcal{R}}_{\omega}(X_{t})+C_{1}\frac{n^{4/3}}{{\omega(n)}^{1/2}}\leq(1-\alpha)\widetilde{\mathcal{R}}_{\omega}(X_{t}),

where the last inequality holds for a suitable constant $\alpha\in(0,1)$ and a sufficiently large $D$ since $\widetilde{\mathcal{R}}_{\omega}(X_{t})>Dn^{4/3}\omega(n)^{-1/2}$ .

On the other hand, Lemma 3.9 implies $\operatorname*{{\rm E}}\left[\mathcal{R}_{1}\left(G\left(A(X_{t}),\frac{q}{n}\right)\right)\right]=O(n^{4/3})$ . By Markov’s inequality, there exists $C_{2}$ such that, with probability $99/100$ ,

\mathcal{R}_{1}\left(G\left(A(X_{t}),\frac{q}{n}\right)\right)\leq C_{2}n^{4/3}.

For large enough $C$ ,

	$\displaystyle\mathcal{R}_{1}(X_{t+1})$	$\displaystyle\leq\mathcal{R}_{1}(K_{t})+\mathcal{R}_{1}\left(G\left(A(X_{t}),\frac{q}{n}\right)\right)\leq\big{(}1-\frac{1}{2q}\big{)}\mathcal{R}_{1}(X_{t})+\mathcal{R}_{1}\left(G\left(A(X_{t}),\frac{q}{n}\right)\right)$
		$\displaystyle\leq\big{(}1-\frac{1}{2q}\big{)}Cn^{4/3}+C_{2}n^{4/3}\leq Cn^{4/3}$

Finally, it follows from a union bound that (7) and (8) hold simultaneously with probability at least $\frac{98}{100\cdot 8q^{2}}$ . ∎

5.2 Coupling to the same large component structure: proof of Lemma 2.7

To prove Lemma 2.7, we use a local limit theorem to construct a two-step coupling of the CM dynamics that reaches two configurations with the same large component structure. The construction of Markov chain couplings using local limit theorems is not common (see [24] for another example), but it appears to be a powerful technique that may have other interesting applications. We provide next a brief introduction to local limit theorems.

Local limit theorem. Let $m$ be an integer. Let $c_{1}\leq\dots\leq c_{m}$ be integers and for $i=1,\dots,m$ , let $X_{i}$ be the random variable that is equal to $c_{i}$ with probability $r\in(0,1)$ , and it is zero otherwise. Let us assume that $X_{1},\dots,X_{m}$ are independent random variables. Let $S_{m}=\sum_{i=1}^{m}X_{i}$ , $\mu_{m}=\operatorname*{{\rm E}}[S_{m}]$ and $\sigma_{m}^{2}=\operatorname*{{\rm Var}}(S_{m})$ . We say that a local limit theorem holds for $S_{m}$ if for every integer $a\in\mathbb{Z}$ :

\Pr[S_{m}=a]=\frac{1}{\sqrt{2\pi}\sigma_{m}}\exp\Big{(}-\frac{(a-\mu_{m})^{2}}{2\sigma_{m}^{2}}\Big{)}+o(\sigma_{m}^{-1}).

(9)

We prove, under some conditions, a local limit theorem that applies to the random variables corresponding to the number of active vertices from small components. Recall that for an increasing positive function $g$ and each integer $k\geq 0$ , we defined the intervals

\mathcal{I}_{k}=\left[\frac{\vartheta m^{2/3}}{2g(m)^{2^{k}}},\frac{\vartheta m^{2/3}}{g(m)^{2^{k}}}\right].

where $\vartheta>0$ is a fixed large constant.

Theorem 5.1.

Let $m$ be an integer. Let $c_{1}\leq\dots\leq c_{m}$ be integers, and suppose $X_{1},...,X_{m}$ are independent random variables such that $X_{i}$ is equal to $c_{i}$ with probability $r\in(0,1)$ , and $X_{i}$ is zero otherwise. Let $g:\mathbb{N}\rightarrow\mathbb{R}$ be an increasing positive function such that $g(m)\rightarrow\infty$ and $g(m)=o(\log m)$ . Suppose $c_{m}=O\left(m^{2/3}g(m)^{-1}\right)$ , $\sum_{i=1}^{m}c_{i}^{2}=O\left(m^{4/3}g(m)^{-1/2}\right)$ and $c_{i}=1$ for all $i\leq\rho m$ , where $\rho\in(0,1)$ is independent of $m$ . Let $\ell=\ell(m,g)>0$ be the smallest integer such that $m^{2/3}g(m)^{-2^{\ell}}=o(m^{1/4})$ . If for all $1\leq k\leq\ell$ , we have $|\{i:c_{i}\in\mathcal{I}_{k}(g)\}|=\Omega(g(m)^{3\cdot 2^{k-1}})$ , then a local limit theorem holds for $S_{m}=\sum_{i=1}^{m}X_{i}$ .

Theorem 5.1 follows from a general local limit theorem proved in [28]; a proof is given in Appendix A. We provide next the proof of Lemma 2.7.

Proof of Lemma 2.7.

First, both $\{X_{t}\}$ , $\{Y_{t}\}$ perform one independent CM step from the initial configurations $X_{0}$ , $Y_{0}$ . We start by establishing that $X_{1}$ and $Y_{1}$ preserve the structural properties assumed for $X_{0}$ and $Y_{0}$ .

By assumption $\mathcal{R}_{1}(X_{0})=O(n^{4/3})$ , so Hoeffding’s inequality implies that the number of activated vertices from $X_{0}$ is such that

A(X_{0})\in I:=\left[n/q-O(n^{2/3}),n/q+O(n^{2/3})\right]

with probability $\Omega(1)$ . Then, the percolation step is distributed as a

G\left(A(X_{0}),\frac{1+\lambda A(X_{0})^{-1/3}}{A(X_{0})}\right)

random graph, with $|\lambda|=O(1)$ with probability $\Omega(1)$ . Conditioning on this event, from Lemma 3.2 we obtain that $I(X_{1})=\Omega(n)$ w.h.p. Moreover, from Lemma 3.9 and Markov’s inequality we obtain that $\mathcal{R}_{1}(X_{1})=O(n^{4/3})$ with probability at least $99/100$ and from Lemma 3.10 that $\widetilde{\mathcal{R}}_{\omega}(X_{1})=O(n^{4/3}{\omega(n)}^{-1/2})$ also with probability at least $99/100$ .

We show next that $X_{1}$ and $Y_{1}$ , in addition to preserving the structural properties of $X_{0}$ and $Y_{0}$ , also have many connected components with sizes in certain carefully chosen intervals. This fact will be crucial in the design of our coupling. When $A(X_{0})\in I$ , by Lemmas 3.11 and 3.12 and a union bound, for all integer $k\geq 0$ such that $n^{2/3}\omega(n)^{-2^{k}}\rightarrow\infty$ , $N_{k}(X_{1},\omega)=\Omega(\omega(n)^{3\cdot 2^{k-1}})$ w.h.p. (Recall, that $N_{k}(X_{1},\omega)$ denotes the number of connected components of $X_{1}$ with sizes in the interval $\mathcal{I}_{k}(\omega)$ .) We will also require a bound for the number of components with sizes in the interval

J=\left[\frac{cn^{2/3}}{\omega(n)^{6}},\frac{2cn^{2/3}}{\omega(n)^{6}}\right],

where $c>0$ is a constant such that $J$ does not intersect any of the $\mathcal{I}_{k}(\omega)$ ’s intervals. Let $W_{X}$ (resp., $W_{Y}$ ) be the set of components of $X_{1}$ (resp., $Y_{1}$ ) with sizes in the interval $J$ . Lemma 3.11 then implies that for some positive constants $\delta_{1},\delta_{2}$ independent of $n$ ,

\Pr\Big{[}|W_{X}|\geq\delta_{1}n\big{(}\frac{\omega(n)^{6}}{cn^{2/3}}\big{)}^{3/2}\Big{]}\geq 1-\frac{\delta_{2}}{n}\Big{(}\frac{cn^{2/3}}{\omega(n)^{6}}\Big{)}^{3/2}=1-O(\omega(n)^{-9}).

All the bounds above apply also to the analogous quantities for $Y_{1}$ with the same respective probabilities. Therefore, by a union bound, all these properties hold simultaneously for both $X_{1}$ and $Y_{1}$ with probability $\Omega(1)$ . We assume that this is indeed the case and proceed to describe the second step of the coupling, in which we shall use each of the established properties for $X_{1}$ and $Y_{1}$ .

Recall $\mathcal{S}_{\omega}(X_{1})$ and $\mathcal{S}_{\omega}(Y_{1})$ denote the sets of connected components in $X_{1}$ and $Y_{1}$ , respectively, with sizes larger than $B_{\omega}$ . (Recall that $B_{\omega}=n^{2/3}\omega(n)^{-1}$ , where $\omega(n)=\log\log\log\log n$ .) Since $\mathcal{R}_{1}(X_{1})=O(n^{4/3})$ , the total number of components in $\mathcal{S}_{\omega}(X_{1})$ is $O(\omega(n)^{2})$ ; moreover, it follows from the Cauchy–Schwarz inequality that the total number of vertices in the components in $\mathcal{S}_{\omega}(X_{1})$ , denoted $\|\mathcal{S}_{\omega}(X_{1})\|$ , is $O(n^{2/3}\omega(n))$ ; the same holds for $\mathcal{S}_{\omega}(Y_{1})$ . Without loss of generality, let us assume that $\|\mathcal{S}_{\omega}(X_{1})\|\geq\|\mathcal{S}_{\omega}(Y_{1})\|$ . Let

\varGamma=\{C\subset W_{Y}:\|\mathcal{S}_{\omega}(Y_{1})\cup C\|\geq\|\mathcal{S}_{\omega}(X_{1})\|\},

and let $C_{\rm min}=\arg\min_{C\in\varGamma}\|\mathcal{S}_{\omega}(Y_{1})\cup C\|$ . In words, $C_{\rm min}$ is the smallest subset $C$ of components of $W_{Y}$ so that the number of vertices in the union of $\mathcal{S}_{\omega}(Y_{1})$ and $C$ is greater than that in $\mathcal{S}_{\omega}(X_{1})$ . Since every component in $W_{Y}$ has size at least $cn^{2/3}\omega(n)^{-6}$ and $|W_{Y}|=\Omega(\omega(n)^{9})$ , the number of vertices in $W_{Y}$ is $\Omega(n^{2/3}\omega(n)^{3})$ and so $\varGamma\neq\emptyset$ . In addition, the number of components in $C_{\rm min}$ is $O(\omega(n)^{9})$ . Let $\mathcal{S}_{\omega}^{\prime}(Y_{1})=\mathcal{S}_{\omega}(Y_{1})\cup C_{\rm min}$ and observe that the number of components in $\mathcal{S}_{\omega}^{\prime}(Y_{1})$ is also $O(\omega(n)^{9})$ and that

0\leq\|\mathcal{S}_{\omega}^{\prime}(Y_{1})\|-\|\mathcal{S}_{\omega}(X_{1})\|\leq 2cn^{2/3}\omega(n)^{-6}.

Note that $\|\mathcal{S}_{\omega}(X_{1})\|-\|\mathcal{S}_{\omega}(Y_{1})\|$ may be $\Omega(n^{2/3}\omega(n))$ (i.e., much larger than $\|\mathcal{S}_{\omega}^{\prime}(Y_{1})\|-\|\mathcal{S}_{\omega}(X_{1})\|$ ). Hence, if all the components from $\mathcal{S}_{\omega}(Y_{1})$ and $\mathcal{S}_{\omega}(X_{1})$ were activated, the difference in the number of active vertices could be $\Omega(n^{2/3}\omega(n))$ . This difference cannot be corrected by our coupling for the activation of the small components. We shall require instead that all the components from $\mathcal{S}_{\omega}^{\prime}(Y_{1})$ and $\mathcal{S}_{\omega}(X_{1})$ are activated so that the difference is $O(n^{2/3}\omega(n)^{-6})$ instead.

We now describe a coupling of the activation sub-step for the second step of the CM dynamics. As mentioned, our goal is to design a coupling in which the same number of vertices are activated from each copy. If indeed $A(X_{1})=A(Y_{1})$ , then we can choose an arbitrary bijective map $\varphi$ between the activated vertices of $X_{1}$ and the activated vertices of $Y_{1}$ and use $\varphi$ to couple the percolation sub-step. Specifically, if $u$ and $v$ were activated in $X_{1}$ , the state of the edges $\{u,v\}$ in $X_{2}$ and $\{\varphi(u),\varphi(v)\}$ in $Y_{2}$ would be the same. This yields a coupling of the percolation sub-step such that $X_{2}$ and $Y_{2}$ agree on the subgraph update at time $1$ .

Suppose then that in the second CM step all the components in $\mathcal{S}_{\omega}(X_{1})$ and $\mathcal{S}_{\omega}^{\prime}(Y_{1})$ are activated simultaneously. If this is the case, then the difference in the number of activated vertices is $d\leq 2cn^{2/3}\omega(n)^{-6}$ . We will use a local limit theorem (i.e., Theorem 5.1) to argue that there is a coupling of the activation of the remaining components in $X_{1}$ and $Y_{1}$ such that the total number of active vertices in both copies is the same with probability $\Omega(1)$ . Since all the components in $\mathcal{S}_{\omega}(X_{1})$ and $\mathcal{S}_{\omega}^{\prime}(Y_{1})$ are activated with probability $\exp(-O(\omega(n)^{9}))$ , the overall success probability of the coupling will be $\exp(-O(\omega(n)^{9}))$ .

Now, let $x_{1},x_{2},\dots,x_{m}$ be the sizes of the components of $X_{1}$ that are not in $\mathcal{S}_{\omega}(X_{1})$ (in increasing order). Let $\hat{A}(X_{1})$ be the random variable corresponding to the number of active vertices from these components. Observe that $\hat{A}(X_{1})$ is the sum of $m$ independent random variables, where the $j$ -th variable in the sum is equal to $x_{j}$ with probability $1/q$ , and it is $0$ otherwise. We claim that sequence $x_{1},x_{2},\dots,x_{m}$ satisfies all the conditions in Theorem 5.1.

First, note that since the number of isolated vertices in $X_{1}$ is $\Omega(n)$ , $m=\Theta(n)$ and consequently $x_{m}=O(m^{2/3}\omega(m)^{-1})$ , $\sum_{i=1}^{m}x_{i}^{2}=\tilde{R}_{\omega}(X_{1})=O(m^{4/3}\omega(m)^{-1/2})$ and $x_{i}=1$ for all $i\leq\rho m$ , where $\rho\in(0,1)$ is independent of $m$ . Moreover, since $N_{k}(X_{1},\omega)=\Omega(\omega(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k}}\rightarrow\infty$ ,

|\{i:x_{i}\in\mathcal{I}_{k}(\omega)\}|=\Omega(\omega(m)^{3\cdot 2^{k-1}}).

Since $N_{0}(X_{1},\omega)=\Omega(\omega(n)^{3/2})$ , we also have

\sum\nolimits_{i=1}^{m}x_{i}^{2}\geq N_{0}(X_{1},\omega)\cdot\frac{\vartheta^{2}n^{4/3}}{4\omega(n)^{2}}=\Omega({m^{4/3}\omega(m)^{-1/2}}).

Let $\mu_{X}=\operatorname*{{\rm E}}[\hat{A}(X_{1})]=q^{-1}\sum_{i=1}^{m}x_{i}$ and let

\sigma_{X}^{2}=\operatorname*{{\rm Var}}(\hat{A}(X_{1}))=q^{-1}(1-q^{-1})\sum_{i=1}^{m}x_{i}^{2}=\Theta(m^{4/3}\omega(m)^{-1/2}).

Hence, Theorem 5.1 implies that $\Pr[\hat{A}(X_{1})=a]=\Omega\left(\sigma_{X}^{-1}\right)$ for any $a\in[\mu_{X}-\sigma_{X},\mu_{X}+\sigma_{X}]$ . Similarly, we get $\Pr[\hat{A}(Y_{1})=a]=\Omega(\sigma_{Y}^{-1})$ for any $a\in[\mu_{Y}-\sigma_{Y},\mu_{Y}+\sigma_{Y}]$ , with $\hat{A}(Y_{1})$ , $\mu_{Y}$ and $\sigma_{Y}$ defined analogously for $Y_{1}$ . Note that $\mu_{X}-\mu_{Y}=O(n^{2/3}\omega(n)^{-6})$ and $\sigma_{X},\sigma_{Y}=\Theta(n^{2/3}\omega(n)^{-1/4})$ . Without loss of generality, suppose $\sigma_{X}<\sigma_{Y}$ . Then for any $a\in[\mu_{X}-\sigma_{X}/2,\mu_{Y}+\sigma_{X}/2]$ and $d=O(n^{2/3}\omega(n)^{-6})$ , we have

\min\left\{\Pr[\hat{A}(X_{1})=a],\Pr[\hat{A}(Y_{1})=a-d]\right\}=\min\left\{\Omega(\sigma_{X}^{-1}),\Omega(\sigma_{Y}^{-1})\right\}=\Omega(\sigma_{Y}^{-1}).

Hence, there exists a coupling $\mathbb{P}$ of $\hat{A}(X_{1})$ and $\hat{A}(Y_{1})$ so that $\mathbb{P}[\hat{A}(X_{1})=a,\hat{A}(Y_{1})=a-d]=\Omega(\sigma_{Y}^{-1})$ for all $a\in\left[\mu_{X}-\sigma_{X}/2,\mu_{Y}+\sigma_{X}/2\right]$ . Therefore, there is a coupling of $\hat{A}(X_{1})$ and $\hat{A}(Y_{1})$ such that

\Pr[\hat{A}(X_{1})-\hat{A}(Y_{1})=d]=\Omega\left({\sigma_{X}}/{\sigma_{Y}}\right)=\Omega(1).

Putting all these together, we deduce that $A(X_{1})=A(Y_{1})$ with probability $\exp(-O(\omega(n)^{9}))$ . If this is the case, the edge re-sampling step is coupled bijectively (as described above) so that $\mathcal{S}_{\omega}(X_{2})=\mathcal{S}_{\omega}(Y_{2})$ .

It remains for us to guarantee the additional desired structural properties of $X_{2}$ and $Y_{2}$ , which follow straightforwardly from the random graph estimates stated in Section 3. First note that by Hoeffding’s inequality, with probability $\Omega(1)$ ,

\left|A(X_{1})-\frac{n}{q}-\frac{(q-1)\|\mathcal{S}_{\omega}(X_{1})\|}{q}\right|=O(n^{2/3}).

Hence, in the percolation sub-step the active subgraph is replaced by $F\sim G\left(A(X_{1}),\frac{1+\lambda A(X_{1})^{-1/3}}{A(X_{1})}\right)$ , where $|\lambda|=O(\omega(n))$ with probability $\Omega(1)$ since $\|\mathcal{S}_{\omega}(X_{1})\|=O(n^{2/3}\omega(n))$ . Conditioning on this event, since the components of $F$ contribute to both $X_{2}$ and $Y_{2}$ , Corollary 3.12 implies that w.h.p. $\hat{N}_{k}(2,\omega(n))$ $=\Omega(\omega(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k}}\rightarrow\infty$ . Moreover, from Lemma 3.2 we obtain that $I(X_{2})=\Omega(n)$ w.h.p. From Lemma 3.4 and Markov’s inequality, we obtain that $\mathcal{R}_{2}(X_{2})=O(n^{4/3})$ with probability at least $99/100$ and from Lemma 3.10 that $\widetilde{\mathcal{R}}_{\omega}(X_{2})=O(n^{4/3}{\omega(n)}^{-1/2})$ also with probability at least $99/100$ . All these bounds apply also to the analogous quantities for $Y_{2}$ with the same respective probabilities.

Finally, we derive the bound for $L_{1}(X_{2})$ and $L_{1}(Y_{2})$ . First, notice $L_{1}(F)$ is stochastically dominated by $L_{1}(F^{\prime})$ , where $F^{\prime}\sim G\Big{(}A(X_{1}),\frac{1+|\lambda|A(X_{1})^{-1/3}}{A(X_{1})}\Big{)}$ . Under the assumption that $|\lambda|=O(\omega(n))$ , if $|\lambda|\rightarrow\infty$ , then Corollary 3.6 implies that $L_{1}(F^{\prime})=O(|\lambda|A(X_{1})^{2/3})=O(n^{2/3}\omega(n))$ w.h.p.; otherwise, $|\lambda|=O(1)$ and by Lemma 3.9 and Markov’s inequality, $L_{1}(F^{\prime})=O(n^{2/3})$ with probability at least $99/100$ . Thus, $L_{1}(F)=O(n^{2/3}\omega(n))$ with probability at least $99/100$ . We also know that the largest inactivated component in $X_{1}$ has size less than $n^{2/3}\omega(n)^{-1}$ , so $L_{1}(X_{2})=O(n^{2/3}\omega(n))$ with probability at least $99/100$ . The same holds for $Y_{2}$ . Therefore, by a union bound, all these properties hold simultaneously for both $X_{2}$ and $Y_{2}$ with probability $\Omega(1)$ , as claimed. ∎

5.3 Re-contracting largest component: proof of Lemma 2.8

In Section 5.2, we designed a coupling argument to ensure that the largest components of both configurations have the same size. For this, we needed to relax our constraint on the size of the largest component of the configurations. In this section we prove Lemma 2.8, which ensures that after $O(\log\omega(n))$ steps the largest components of each configuration have size $O(n^{2/3})$ again.

The following lemma is the core of the proof Lemma 2.8 and it may be viewed as a generalization of the coupling from the proof of Lemma 2.7 using the local limit theorem from Section 5.2.

We recall some notation from the proof sketch. Given two random-cluster configurations $X_{t}$ and $Y_{t}$ , $W_{t}$ is maximal matching between the components of $X_{t}$ and $Y_{t}$ that only matches components of equal size to each other. We use $M(X_{t})$ , $M(Y_{t})$ for the components in $W_{t}$ from $X_{t}$ , $Y_{t}$ , respectively, $D(X_{t})$ , $D(Y_{t})$ for the complements of $M(X_{t})$ , $M(Y_{t})$ , and $Z_{t}=\sum_{\mathcal{C}\in D(X_{t})\cup D(Y_{t})}|\mathcal{C}|^{2}.$ For an increasing positive function $g$ and each integer $k\geq 1$ , define $\hat{N}_{k}(t,g):=\hat{N}_{k}(X_{t},Y_{t},g)$ as the number of matched pairs in $W_{t}$ whose component sizes are in the interval

\mathcal{I}_{k}(g)=\left[\frac{\vartheta n^{2/3}}{2g(n)^{2^{k}}},\frac{\vartheta n^{2/3}}{g(n)^{2^{k}}}\right],

where $\vartheta>0$ is a fixed large constant (independent of $n$ ).

Lemma 5.2.

There exists a coupling of the activation sub-step of the CM dynamics such that $A(X_{t})=A(Y_{t})$ with at least $\Omega\left(\frac{1}{\omega(n)}\right)$ probability, provided $X_{t}$ and $Y_{t}$ are random-cluster configurations satisfying

1.

$\mathcal{S}_{\omega}(X_{t})=\mathcal{S}_{\omega}(Y_{t})$ ;
2.

$Z_{t}=O\left(\frac{n^{4/3}}{\omega(n)^{1/2}}\right)$ ;
3.

$\hat{N}_{k}(X_{t},Y_{t},\omega(n))=\Omega\left(\omega(n)^{3\cdot 2^{k-1}}\right)$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k}}\rightarrow\infty$ ;
4.

$I(X_{t}),I(Y_{t})=\Omega(n)$ .

Proof.

The activation coupling has two parts. First we use the maximal matching $W_{t}$ to couple the activation of a subset of the components in $M(X_{t})$ and $M(Y_{t})$ . Specifically, let $\ell$ be defined as in Theorem 5.1; for all $k\in[1,\ell]$ , we exclude $\Theta(\omega(n)^{3\cdot 2^{k-1}})$ pairs of components of size in the interval $\mathcal{I}_{k}(\omega)$ and we exclude $\Theta(n)$ pairs of matched isolated vertices. (These components exist by assumptions 3 and 4.) All other pairs of components matched by $W_{t}$ are jointly activated (or not). Hence, the number of vertices activated from $X_{t}$ in this first part of the coupling is the same as that from $Y_{t}$ .

Let $\mathcal{C}(X_{t})$ and $\mathcal{C}(Y_{t})$ denote the sets containing the components in $X_{t}$ and components in $Y_{t}$ not considered to be activated in the first step of the coupling. This includes all the components from $D(X_{t})$ and $D(Y_{t})$ , and all the components from $M(X_{t})$ and $M(Y_{t})$ excluded in the first part of the coupling. Let $A^{\prime}(X_{t})$ and $A^{\prime}(Y_{t})$ denote the number of activated vertices from $\mathcal{C}(X_{t})$ and $\mathcal{C}(Y_{t})$ respectively. The second part is a coupling of the activation sub-step in a way such that

\Pr\left[A^{\prime}(X_{t})=A^{\prime}(Y_{t})\right]=\Omega(\omega(n)^{-1}).

Let $m_{x}:=|\mathcal{C}(X_{t})|=\Theta(n)$ , and similarly for $m_{y}:=|\mathcal{C}(Y_{t})|$ . Let $\mathcal{C}_{1}\leq\dots\leq\mathcal{C}_{m_{x}}$ (resp., $\mathcal{C^{\prime}}_{1}\leq\dots\leq\mathcal{C^{\prime}}_{m_{y}}$ ) be sizes of components in $\mathcal{C}(X_{t})$ (resp., $\mathcal{C}(Y_{t})$ ) in ascending order. For all $i\leq m_{x}$ , let $\mathcal{X}_{i}$ be a random variable that equals to $\mathcal{C}_{i}$ with probability $1/q$ and $0$ otherwise, which corresponds to the number of activated vertices from $i$ th component in $\mathcal{C}(X_{t})$ . Note that $\mathcal{X}_{1},\dots,\mathcal{X}_{m_{x}}$ are independent. We check that $\mathcal{X}_{1},\dots,\mathcal{X}_{m_{x}}$ satisfy all other conditions of Theorem 5.1.

Assumption $\mathcal{S}_{\omega}(X_{t})=\mathcal{S}_{\omega}(Y_{t})$ and the first part of the activation ensure that

\mathcal{C}_{m_{x}}\leq B_{\omega}=O\left(n^{2/3}\omega(n)^{-1}\right)=O\left(m_{x}^{2/3}\omega(m_{x})^{-1}\right).

Observe also that there exists a constant $\rho$ such that $\mathcal{C}_{i}=1$ for $i\leq\rho m_{x}$ and $\lvert\{i:\mathcal{C}_{i}\in\mathcal{I}_{k}(\omega)\}\rvert=\Theta\left(\omega(n)^{3\cdot 2^{k-1}}\right)$ for $1\leq k\leq\ell$ ; lastly, from assumption $Z_{t}=O\left(\frac{n^{4/3}}{\omega(n)^{1/2}}\right)$ , we obtain

$\displaystyle\sum_{i=1}^{m_{x}}\mathcal{C}_{i}^{2}$	$\displaystyle\leq Z_{t}+O(\rho m_{x})+\sum_{k=1}^{\ell}\frac{\vartheta n^{4/3}}{\omega(n)^{2^{k+1}}}\cdot O\left(\omega(n)^{3\cdot 2^{k-1}}\right)$
	$\displaystyle=O\left(\frac{m_{x}^{4/3}}{\sqrt{\omega(m_{x})}}\right)+O\left(\sum_{k=1}^{\ell}\frac{m_{x}^{4/3}}{\omega(m_{x})^{2^{k-1}}}\right)$
	$\displaystyle=O\left(\frac{m_{x}^{4/3}}{\sqrt{\omega(m_{x})}}\right)+O\left(\sum_{k=1}^{\ell}\frac{m_{x}^{4/3}}{\omega(m_{x})^{k}}\right)$
	$\displaystyle=O\left(\frac{m_{x}^{4/3}}{\sqrt{\omega(m_{x})}}\right)+O\left(\frac{m_{x}^{4/3}}{\omega(m_{x})}\right)=O\left(\frac{m_{x}^{4/3}}{\sqrt{\omega(m_{x})}}\right).$	(10)

Therefore, if $\mu_{x}=\operatorname*{{\rm E}}\left[\sum_{i=1}^{m_{x}}\mathcal{X}_{i}\right]$ and $\sigma_{x}^{2}=Var\left(\sum_{i=1}^{m_{x}}\mathcal{X}_{i}\right)$ , Theorem 5.1 implies that for any $x\in[\mu_{x}-\sigma_{x},\mu_{x}+\sigma_{x}]$ ,

\Pr\left[A^{\prime}(X_{t})=x\right]=\Pr\left[\sum_{i=1}^{m_{x}}\mathcal{X}_{i}=x\right]=\frac{1}{\sqrt{2\pi}\sigma_{x}}\exp\left(-\frac{(x-\mu_{x})^{2}}{2\sigma_{x}^{2}}\right)+o\left(\frac{1}{\sigma_{x}}\right)=\Omega\left(\frac{1}{\sigma_{x}}\right).

Similarly, we get that $\Pr\left[A^{\prime}(Y_{t})=y\right]=\Omega(\sigma_{y}^{-1})$ for any $y\in[\mu_{y}-\sigma_{y},\mu_{y}+\sigma_{y}]$ , with $\mu_{y}$ and $\sigma_{y}$ defined analogously. Without loss of generality, suppose $\sigma_{y}\leq\sigma_{x}$ . Since $\mu_{x}=\mu_{y}$ , for $x\in\left[\mu_{x}-\sigma_{y},\mu_{x}+\sigma_{y}\right]$ , we obtain

\min\left\{\Pr\left[A^{\prime}(X_{t})=x\right],\Pr\left[A^{\prime}(Y_{t})=x\right]\right\}=\Omega\left(\frac{1}{\sigma_{x}}\right).

Hence, we can couple $(A^{\prime}(X_{t}),A^{\prime}(Y_{t}))$ so that $\Pr[A^{\prime}(X_{t})=A^{\prime}(Y_{t})=x]=\Omega(\sigma_{x}^{-1})$ for all $x\in[\mu_{x}-\sigma_{y},\mu_{x}+\sigma_{y}]$ . Consequently, under this coupling,

\Pr\left[A^{\prime}(X_{t})=A^{\prime}(Y_{t})\right]=\Omega\left(\frac{\sigma_{y}}{\sigma_{x}}\right).

Since $\mathcal{X}_{1},\dots,\mathcal{X}_{m_{x}}$ are independent, $\sigma_{x}^{2}=\Theta\left(\sum_{i=1}^{m_{x}}\mathcal{C}_{i}^{2}\right)$ , and similarly $\sigma_{y}^{2}=\Theta\left(\sum_{i=1}^{m_{y}}\mathcal{C^{\prime}}_{i}^{2}\right)$ . Hence, inequality (10) gives an upper bound for $\sigma_{x}^{2}$ ; meanwhile, a lower bound for $\sigma_{y}^{2}$ can be obtained by counting components in the largest interval:

\sum_{i=1}^{m_{y}}\mathcal{C^{\prime}}_{i}^{2}\geq\sum_{i:\mathcal{C^{\prime}}_{i}\in\mathcal{I}_{1}(\omega)}\mathcal{C^{\prime}}_{i}^{2}\geq\frac{Bn^{4/3}}{\omega(n)^{4}}\cdot\Theta\left(\omega(n)^{3}\right)=\Omega\left(\frac{n^{4/3}}{\omega(n)}\right).

Therefore,

\Pr\left[A^{\prime}(X_{t})=A^{\prime}(Y_{t})\right]=\Omega\left(\frac{n^{2/3}}{\omega(n)^{1/2}}\cdot\frac{\omega(m_{x})^{1/4}}{m_{x}^{2/3}}\right)=\Omega\left(\frac{1}{\omega(n)}\right),

as desired. ∎

We are now ready to prove Lemma 2.8.

Proof of Lemma 2.8.

Let $C_{1}$ be a suitable constant that we choose later. We wish to maintain the following properties for all $t\leq T:=C_{1}\log\omega(n)$ :

1.

$\mathcal{S}_{\omega}(X_{t})=\mathcal{S}_{\omega}(Y_{t})$ ;
2.

$Z_{t}=O\left(\frac{n^{4/3}}{\omega(n)^{1/2}}\right)$ ;
3.

$\hat{N}_{k}(X_{t},Y_{t},\omega(n))=\Omega\left(\omega(n)^{3\cdot 2^{k-1}}\right)$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k}}\rightarrow\infty$ ;
4.

$I(X_{t}),I(Y_{t})=\Omega(n)$ ;
5.

$\mathcal{R}_{2}(X_{t}),\mathcal{R}_{2}(Y_{t})=O(n^{4/3})$ ;
6.

$L_{1}(X_{t})\leq\alpha^{t}L_{1}(X_{0}),L_{1}(Y_{t})\leq\alpha^{t}L_{1}(Y_{0})$ for some constant $\alpha$ independent of $t$ .

By assumption, $X_{0}$ and $Y_{0}$ satisfy these properties. Suppose that $X_{t}$ and $Y_{t}$ satisfy these properties at step $t\leq T$ . We show that there exists a one-step coupling of the CM dynamics such that $X_{t+1}$ and $Y_{t+1}$ preserve all six properties with probability $\Omega\left(\omega(n)^{-1}\right)$ .

We provide the high-level ideas of the proof first. We will crucially exploit the coupling from Lemma 5.2. Assuming $A(X_{t})=A(Y_{t})$ , properties 1 and 2 hold immediately at $t+1$ , and properties 3 and 4 can be shown by a “standard” approach used throughout the paper. In addition, we reuse simple arguments from previous stages to guarantee properties 5 and 6.

Consider first the activation sub-step. By Lemma 5.2, $A(X_{t})=A(Y_{t})$ with probability at least $\Omega(\omega(n)^{-1})$ . If the number of vertices in the percolation is the same in both copies, we can couple the edge re-sampling so that the updated part of the configuration is identical in both copies. In other words, all new components created in this step are automatically contained in the component matching $W_{t+1}$ ; this includes all new components whose sizes are greater than $B_{\omega}$ . Since none of the new components contributes to $Z_{t+1}$ , we obtain $Z_{t+1}\leq Z_{t}=O\left(\frac{n^{4/3}}{\omega(n)^{1/2}}\right)$ . Therefore, $A(X_{t})=A(Y_{t})$ immediately implies properties 1 and 2 at time $t+1$ .

With probability $1/q$ , the largest components of $X_{t}$ and $Y_{t}$ are activated simultaneously. Suppose that this is the case. By Hoeffding’s inequality, for constant $K>0$ , we have

\Pr\left[\left\lvert A(X_{t})-\operatorname*{{\rm E}}\left[A(X_{t})\right]\right\rvert\geq Kn^{2/3}\right]\leq\exp\left(-\frac{K^{2}n^{4/3}}{\mathcal{R}_{2}(X_{t})}\right).

Property 5 and the observation that $\operatorname*{{\rm E}}\left[A(X_{t})\right]=L_{1}(X_{t})+\frac{n-L_{1}(X_{t})}{q}$ imply that

\Pr\left[\left\lvert A(X_{t})-L_{1}(X_{t})-\frac{n-L_{1}(X_{t})}{q}\right\rvert\geq Kn^{2/3}\right]=O(1).

By noting that $L_{1}(Y_{0}),L_{1}(X_{0})\leq n^{2/3}\omega(n)$ , property 6 implies that

\Pr\left[A(X_{t})\cdot\frac{q}{n}\leq 1+\frac{(q-1)\omega(n)+Kq}{n^{1/3}}\right]=\Omega(1).

(11)

We denote $A(X_{t})=A(Y_{t})$ by $m$ . By inequality (11), with at least constant probability, the random graph for both chains is $H\sim G\left(m,\frac{1+\lambda m^{-1/3}}{m}\right)$ , where $\lambda\leq\omega(m)$ . Let us assume that is the case. Corollary 3.12 ensures that there exists a constant $b>0$ such that, with probability at least $1-O(\omega(n)^{-3})$ , $N_{k}(H,\omega(n))\geq b\omega(n)^{3\cdot 2^{k-1}}$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k}}\rightarrow\infty$ . Since components in $H$ are simultaneously added to both $X_{t+1}$ and $Y_{t+1}$ , property 3 is satisfied. Moreover, Lemma 3.2 implies that with high probability $\Omega(n)$ isolated vertices are added to $X_{t+1}$ and $Y_{t+1}$ , and thus property 4 is satisfied at time $t+1$ .

In addition, Lemma 3.4 and Markov’s inequality imply that there exists a constant $C_{2}$ such that

\Pr\left[\mathcal{R}_{2}(X_{t+1})=C_{2}n^{4/3}\right]\geq\frac{99}{100};

By Lemma 4.3, there exists $\alpha<1$ such that with at least probability $99/100$

L_{1}(X_{t+1})\leq\max\{\alpha L_{1}(X_{t}),L_{2}(X_{t})\},

where $\alpha$ is independent of $t$ and $n$ . Potentially, property 6 may not hold when $\alpha L_{1}(X_{t})<L_{1}(X_{t+1})\leq L_{2}(X_{t})=O(n^{2/3})$ , but then we stop at this point. (We will argue that in this case all the desired properties are also established shortly.) Hence, we suppose otherwise and establish properties 5 and 6 for $X_{t+1}$ . Similar bounds hold for $Y_{t+1}$ .

By a union bound, $X_{t+1}$ and $Y_{t+1}$ have all six properties with probability at least $92/100$ , assuming the activation sub-step satisfies all the desired properties, and thus overall with probability $\Omega\left(\omega(n)^{-1}\right)$ . Inductively, the probability that $X_{T}$ and $Y_{T}$ satisfy the six properties is

O\left(\omega(n)\right)^{-C_{1}\log\omega(n)}=\exp\left(\log O(\omega(n))^{-C_{1}\log\omega(n)}\right)=\exp\left(-O\left((\log\omega(n))^{2}\right)\right).

Suppose $X_{T}$ and $Y_{T}$ have the six properties. By choosing $C_{1}>1/\log\frac{1}{\alpha}$ , properties 5 and 6 imply

\mathcal{R}_{1}(X_{T})=L_{1}(X_{T})^{2}+\mathcal{R}_{2}(X_{T})\leq\left(\alpha^{C_{1}\log\omega(n)}n^{2/3}\omega(n)\right)^{2}+O(n^{4/3})=O(n^{4/3}),

and $\mathcal{R}_{1}(Y_{T})=O(n^{4/3})$ . While the lemma almost follows from these properties, notice that property 3 does not match the desired bounds on the components in the lemma statement. To fix this issue, we perform one additional step of the coupling.

Consider the activation sub-step at $T$ . Assume again $A(X_{T})=A(Y_{T})=:m^{\prime}$ . By Hoeffding’s inequality, for some constant $K^{\prime}$ , we obtain

\Pr\left[\left|m^{\prime}\cdot\frac{q}{n}-1\right|>\frac{K^{\prime}}{n^{1/3}}\right]=\Pr\left[\left|m^{\prime}-\frac{n}{q}\right|>K^{\prime}n^{2/3}\right]\leq\exp\left(\frac{-{K^{\prime}}^{2}n^{4/3}}{\mathcal{R}_{1}(X_{T})}\right)=O(1).

(12)

Let $\lambda^{\prime}:=(m^{\prime}qn^{-1}-1)\cdot m^{\prime 1/3}$ . Inequality (12) implies with at least constant probability the random graph in the percolation step is $H^{\prime}\sim G\left(m^{\prime},\frac{1+\lambda^{\prime}m^{\prime-1/3}}{m^{\prime}}\right)$ , where $\lambda^{\prime}\leq K^{\prime}$ and $m^{\prime}\in(n/2q,n)$ . If so, Corollary 3.12 ensures with high probability $\hat{N}_{k}(X_{T+1},Y_{T+1},\omega(n)^{1/2})=\Omega\left({\omega(n)}^{3\cdot 2^{k-2}}\right)$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k-1}}\rightarrow\infty$ .

By the preceding argument, with $\Omega(\omega(n)^{-1})$ probability, the six properties are still valid at step $T+1$ , so the proof is complete. We note that if we had to stop earlier because property 6 did not hold, we perform one extra step (as above) to ensure that $\hat{N}_{k}(X_{T+1},Y_{T+1},\omega(n)^{1/2})=\Omega({\omega(n)}^{3\cdot 2^{k-2}})$ for all $k\geq 1$ such that $n^{2/3}\omega(n)^{-2^{k-1}}\rightarrow\infty$ . ∎

5.4 A four-phase analysis using random walks couplings: proof of Lemma 2.9

We introduce first some notation that will be useful in the proof of Lemma 2.9. Let $S(X_{0})=\emptyset$ , and given $S(X_{t})$ , $S(X_{t+1})$ is obtained as follows:

(i)

$S(X_{t+1})=S(X_{t})$ ;
(ii)

every component in $S(X_{t})$ activated by the CM dynamics at time $t$ is removed from $S(X_{t+1})$ ; and
(iii)

the largest new component (breaking ties arbitrarily) is added to $S(X_{t+1})$ .

Let $\mathcal{C}(X_{t})$ denote the set of connected components of $X_{t}$ and note that $S(X_{t})$ is a subset of $\mathcal{C}(X_{t})$ ; we use $|S(X_{t})|$ to denote the total number of vertices of the components in $S(X_{t})$ . Finally, let

Q(X_{t})=\sum_{\mathcal{C}\in\mathcal{C}(X_{t})\setminus S(X_{t})}|\mathcal{C}|^{2}.

In the proof of Lemma 2.9, we use the following lemmas.

Lemma 5.3.

Let $r$ be an increasing positive function such that $r(n)=o(n^{1/15})$ and let $c>0$ be a sufficiently large constant. Suppose $|S(X_{t})|\leq ctn^{2/3}r(n)$ , $Q(X_{t})\leq tn^{4/3}r(n)+O(n^{4/3})$ and $t\leq r(n)/\log r(n)$ . Then, with probability at least $1-O\left(r(n)^{-1}\right)$ , $|S(X_{t+1})|\leq c(t+1)n^{2/3}r(n)$ and $Q(X_{t+1})\leq(t+1)n^{4/3}r(n)+O(n^{4/3})$ .

Lemma 5.4.

Let $f$ be a positive function such that $f(n)=o(n^{1/3})$ . Suppose a configuration $X_{t}$ satisfies $\mathcal{R}_{1}(X_{t})=O\left(n^{4/3}f(n)^{2}(\log f(n))^{-1}\right)$ . Let $m$ denote the number of activated vertices in this step, and $\lambda:=(mq/n-1)\cdot m^{1/3}$ . With probability $1-O\left(f(n)^{-1}\right)$ , $m\in(n/2q,n)$ and $|\lambda|\leq f(n)$ .

Lemma 5.5.

Let $g$ and $h$ be two increasing positive functions of $n$ . Assume $g(n)=o(n^{1/6})$ . Let $X_{t}$ and $Y_{t}$ be two random-cluster configuration such that $\hat{N}_{k}(X_{t},Y_{t},g)\geq bg(n)^{3\cdot 2^{k-1}}$ for some fixed constant $b>0$ independent of $n$ and for all $k\geq 1$ such that $n^{2/3}g(n)^{-2^{k}}\rightarrow\infty$ . Assume also that $Z_{t}\leq Cn^{4/3}h(n)^{-1}$ for some constant $C>0$ . Lastly, assume $I(X_{t}),I(Y_{t})=\Omega(n)$ . Then for every positive function $\eta$ there exists a coupling for the activation sub-step of the components of $X_{t}$ and $Y_{t}$ such that

\Pr[A(X_{t})=A(Y_{t})]\geq 1-4e^{-2\eta(n)}-\sqrt{\frac{g(n)\eta(n)}{h(n)}}-\frac{\delta}{g(n)},

for some constant $\delta>0$ independent of $n$ .

The proofs of these lemmas are given in Section 5.4.1. In particular, as mentioned, to prove Lemma 5.5 we use a precise estimate on the maximum of a random walk on $\mathbb{Z}$ with steps of different sizes (see Theorem 5.7).

Proof of Lemma 2.9.

The coupling has four phases: in phase 1 we will consider $O(\log\log\log\log n)$ steps of the coupling, $O(\log\log\log n)$ steps in phase 2, $O(\log\log n)$ steps in phase 3 and phase 4 consists of $O(\log n)$ steps.

We will keep track of the random variables $\mathcal{R}_{1}(X_{t}),\mathcal{R}_{1}(Y_{t}),I(X_{t}),I(Y_{t}),Z_{t}$ and $\hat{N}_{k}(t,g)$ for a function $g$ we shall carefully choose for each phase, and use these random variables to derive bounds on the probability of various events.

Phase 1. We set $g_{1}(n)=\omega(n)^{1/2}$ and $h_{1}(n)=K^{2}\omega(n)^{1/2}$ where $K>0$ is a constant we choose. Let $a_{1}:=1-\frac{1}{2q}$ and let $T_{1}:=-12\log_{a_{1}}(\log\log\log n)$ , and we fix $t<T_{1}$ . Suppose we have $\mathcal{R}_{1}(X_{t})+\mathcal{R}_{1}(Y_{t})\leq C_{1}n^{4/3}$ , $I(X_{t}),I(Y_{t})=\Omega(n)$ , and $\hat{N}_{k}(t,g_{1})=\Omega(g_{1}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{1}(n)^{-2^{k}}\rightarrow\infty$ , where $C_{1}>0$ is a large constant that we choose later.

By Lemma 5.5, for a sufficiently large constant $K>0$ , we obtain a coupling for the activation of $X_{t}$ and $Y_{t}$ such that the same number of vertices are activated in $X_{t}$ and $Y_{t}$ , with probability at least

1-4e^{-2K}-\sqrt{\frac{K\omega(n)^{1/2}}{K^{2}\omega(n)^{1/2}}}-\frac{\delta}{\omega(n)^{1/2}}\geq 1-\frac{1}{16q^{2}}.

By Lemma 5.4, $A(X_{t})\in(n/2q,n)$ and $\lambda:=(A(X_{t})q/n-1)\cdot A(X_{t})^{1/3}=O(1)$ with probability at least $1-\frac{1}{16q^{2}}$ . It follows a union bound that $A(X_{t})=A(Y_{t})$ , $A(X_{t})\in(n/2q,n)$ and $\lambda=O(1)$ with probability $1-\frac{1}{8q^{2}}$ . We call this event $\mathcal{H}^{1}_{t}$ .

Let $D_{t}^{\prime}$ denote the inactivated components in $D(X_{t})\cup D(Y_{t})$ at the step $t$ , and $M_{t}^{\prime}$ the inactivated components in $M(X_{t})\cup M(X_{t})$ . Observe that

\operatorname*{{\rm E}}\left[\sum\nolimits_{\mathcal{C}\in D_{t}^{\prime}}|\mathcal{C}|^{2}\right]=\left(1-\frac{1}{q}\right)\sum\nolimits_{\mathcal{C}\in D(X_{t})\cup D(Y_{t})}|\mathcal{C}|^{2}=\left(1-\frac{1}{q}\right)Z_{t}.

Similarly,

\operatorname*{{\rm E}}\left[\sum\nolimits_{\mathcal{C}\in M_{t}^{\prime}}|\mathcal{C}|^{2}\right]=\left(1-\frac{1}{q}\right)\sum\nolimits_{\mathcal{C}\in M(X_{t})\cup M(Y_{t})}|\mathcal{C}|^{2}=\left(1-\frac{1}{q}\right)\left(\mathcal{R}_{1}(X_{t})+\mathcal{R}_{1}(Y_{t})-Z_{t}\right).

Hence, by Markov’s inequality and independence between activation of components in $D_{t}^{\prime}$ and components in $M_{t}^{\prime}$ , with probability at least $1/4q^{2}$ , the activation sub-step is such that

\sum\nolimits_{\mathcal{C}\in D_{t}^{\prime}}|\mathcal{C}|^{2}\leq\left(1-\frac{1}{2q}\right)Z_{t},

and

\sum\nolimits_{\mathcal{C}\in M_{t}^{\prime}}|\mathcal{C}|^{2}\leq\left(1-\frac{1}{2q}\right)\left(\mathcal{R}_{1}(X_{t})+\mathcal{R}_{1}(Y_{t})-Z_{t}\right).

We denote this event by $\mathcal{H}^{2}_{t}$ . By a union bound, $\mathcal{H}^{1}_{t}$ and $\mathcal{H}^{2}_{t}$ happen simultaneously with probability $1/8q^{2}$ .

Suppose all these events indeed happen; then we couple the percolation step so that the components newly generated in both copies are exactly identical, and we claim that all of the following holds with at least constant probability:

1.

$\mathcal{R}_{1}(X_{t+1})+\mathcal{R}_{1}(Y_{t+1})\leq C_{1}n^{4/3}$ ;
2.

$Z_{t+1}\leq a_{1}Z_{t}$ ;
3.

$I(X_{t+1}),I(Y_{t+1})=\Omega(n)$ ;
4.

$\hat{N}_{k}(t+1,g_{1})=\Omega(g_{1}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{1}(n)^{-2^{k}}\rightarrow\infty$ .

First, note that $Z_{t+1}$ can not possibly increase because the matching $W_{t+1}$ can only grow under the coupling if indeed $A(X_{t})=A(Y_{t})$ . Observe that only the inactivated components in $X_{t}$ and $Y_{t}$ would contribute to $Z_{t+1}$ , so

Z_{t+1}=\sum\nolimits_{\mathcal{C}\in D_{t}^{\prime}}|\mathcal{C}|^{2}\leq a_{1}Z_{t}.

Next, we establish the properties 3 and 4. For this, notice that the percolation step is distributed as a $H\sim$ $G\left(A(X_{t}),\frac{1+\lambda A(X_{t})^{-1/3}}{A(X_{t})}\right)$ random graph. Corollary 3.12 implies $N_{k}(H,g_{1})=\Omega(g_{1}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{1}(n)^{-2^{k}}\rightarrow\infty$ , with probability at least $1-O\left(g_{1}(n)^{-3}\right)$ . Moreover, Lemma 3.2 implies that with high probability $I(H)=\Omega(n)$ . Since the percolation step is coupled, this implies that both $X_{t+1}$ and $Y_{t+1}$ will have all the components in $H$ , so we have $\hat{N}_{k}(t+1,g_{1})=\Omega(g_{1}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{1}(n)^{-2^{k}}\rightarrow\infty$ , and $I(X_{t+1}),I(Y_{t+1})=\Omega(n)$ , w.h.p.

Finally, assuming that $|\lambda|=O(1)$ , by Lemma 3.9 and Markov’s inequality, there exists $C_{2}>0$ such that $\operatorname*{{\rm E}}\left[\mathcal{R}_{1}(H)\right]=C_{2}n^{4/3}$ with probability at least $99/100$ . Then

	$\displaystyle\mathcal{R}_{1}(X_{t+1})+\mathcal{R}_{1}(Y_{t+1})$	$\displaystyle=\sum\nolimits_{\mathcal{C}\in D_{t}^{\prime}}\|\mathcal{C}\|^{2}+\sum\nolimits_{\mathcal{C}\in M_{t}^{\prime}}\|\mathcal{C}\|^{2}+\mathcal{R}_{1}(H)$
		$\displaystyle\leq a_{1}\left(\mathcal{R}_{1}(X_{t})+\mathcal{R}_{1}(Y_{t})\right)+C_{2}n^{4/3}\leq a_{1}C_{1}n^{4/3}+C_{2}n^{4/3}\leq C_{1}n^{4/3},$

for large enough $C_{1}$ . A union bound implies that all four properties hold with at least constant probability $\varrho>0$ .

Thus, the probability that at each step of update all four properties can be maintained throughout Phase 1 is at least

\varrho^{T_{1}}=\varrho^{-12\log_{a_{1}}(\log\log\log n)}=\left(\log\log\log n\right)^{-12\log_{\varrho}(a_{1})}.

If property 2 holds at the end of Phase 1, we have

Z_{T_{1}}=O\left(\frac{n^{4/3}}{h_{1}(n)}\cdot a_{1}^{T_{1}}\right)=O\left(\frac{n^{4/3}}{h_{1}(n)}\cdot a_{1}^{-12\log_{a_{1}}(\log\log\log n)}\right)=O\left(\frac{n^{4/3}}{(\log\log\log n)^{12}}\right).

To facilitate discussions in Phase 2, we show that the two copies of chains satisfy one additional property at the end of Phase 1. In particular, there exist a lower bound for the number of components in a different set of intervals. We consider the last percolation step in Phase 1. Then, Corollary 3.12 with $g_{2}(n):=\left(\log\log\log n\cdot\log\log\log\log n\right)^{2}$ implies $\hat{N}_{k}(T_{1},g_{2})=\Omega(g_{2}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{2}(n)^{-2^{k}}\rightarrow\infty$ , with high probability.

Recall $S(X)$ and $Q(X)$ defined at the beginning of Section 5.4. In Phase 2, 3 and 4, a new element of the argument is to also control the behavior $S(X_{t})$ and $Q(X_{t})$ . We provide a general result that will be used in the analysis of the three phases:

Claim 5.6.

Given positive increasing functions $T,g,h$ and $r$ that tend to infinity and satisfy

1.

$g(n)=o(n^{1/6})$ ;
2.

$T=o(g)$ ;
3.

$r(n)=o(n^{1/15})$ ;
4.

$T(n)^{2}\cdot r(n)^{2}\leq g(n)^{2}/\log g(n)$ ;
5.

$T(n)\leq r(n)/\log r(n)$ ;
6.

$g(n)\log g(n)\leq h(n)^{1/3}$ .

and random-cluster configurations $X_{0},Y_{0}$ satisfying

1.

$Z_{0}=O\left(\frac{n^{4/3}}{h(n)}\right)$ ;
2.

$|S(X_{0})|,|S(Y_{0})|\leq n^{2/3}r(n)$ ;
3.

$Q(X_{0}),Q(Y_{0})=O(n^{4/3}r(n))$ ;
4.

$I(X_{0}),I(Y_{0})=\Omega(n)$ ;
5.

$\hat{N}_{k}(0,g)=\Omega\left(g(n)^{3\cdot 2^{k-1}}\right)$ for all $k\geq 1$ such that $n^{2/3}g(n)^{-2^{k}}\rightarrow\infty$ .

There exists a coupling of CM steps such that after $T=T(n)$ steps, with $\Omega(1)$ probability,

1.

$Z_{T}=O\left(\frac{n^{4/3}}{a^{T(n)}}\right)$ ;
2.

$|S(X_{T})|,|S(Y_{T})|=O(n^{2/3}r(n)T(n))$ ;
3.

$Q(X_{T}),Q(Y_{T})=O(n^{4/3}r(n)T(n))$ ;
4.

$I(X_{T}),I(Y_{T})=\Omega(n)$ ;
5.

If a function $g^{\prime}$ satisfies $g^{\prime}\geq g$ and $g^{\prime}(n)=o(n^{1/3})$ , then $\hat{N}_{k}(T,g^{\prime})=\Omega\left(g^{\prime}(n)^{3\cdot 2^{k-1}}\right)$ for all $k\geq 1$ such that $n^{2/3}g^{\prime}(n)^{-2^{k}}\rightarrow\infty$ .

Proof of this claim is provided later in Section 5.4.1.

Phase 2. Let $a=q/(q-1)$ . For Phase 2, we set $g_{2}(n)=\left(\log\log\log n\cdot\log\log\log\log n\right)^{2}$ , $g_{3}(n)=(\log\log n\cdot\log\log\log n)^{2}$ , $h_{2}(n)=\left(\log\log\log n\right)^{12}$ , $r_{2}(n)=13\log_{a}\log\log n\cdot\log\log_{a}\log\log n$ and $T_{2}=T_{1}+12\log_{a}\log\log n$ . Notice these functions satisfy the conditions of 5.6:

1.

$g_{2}(n)=o(n^{1/6})$ ;
2.

$T_{2}-T_{1}=o(g_{2}(n))$ ;
3.

$r_{2}(n)=o(n^{1/15})$ ;
4.

$(T_{2}-T_{1})^{2}r_{2}(n)^{2}\leq 10^{6}(\log_{a}\log\log n)^{4}(\log\log_{a}\log\log n)^{2}\leq g_{2}(n)^{2}/\log g_{2}(n)$ ;
5.

$T_{2}-T_{1}=12\log_{a}\log\log n\leq r_{2}(n)/\log r_{2}(n)$ ;
6.

$g_{2}(n)/\log g_{2}(n)\leq\left(\log\log\log n\right)^{4}=h_{2}(n)^{1/3}$ .

Suppose that we have all the desired properties from Phase 1, so at the beginning of Phase 2 we have:

1.

$Z_{T_{1}}=O\left(\frac{n^{4/3}}{(\log\log\log n)^{12}}\right)=O\left(\frac{n^{4/3}}{h_{2}(n)}\right)$ ;
2.

$S(X_{T_{1}})\leq\sqrt{R_{1}(X_{T_{1}})}\leq n^{2/3}r_{2}(n)$ , $S(Y_{T_{1}})=\sqrt{R_{1}(Y_{T_{1}})}\leq n^{2/3}r_{2}(n)$ ;
3.

$I(X_{T_{1}})=\Omega(n),I(Y_{T_{1}})=\Omega(n)$ ;
4.

$Q(X_{T_{1}})\leq R_{1}(X_{T_{1}})=O(n^{4/3})$ , $Q(Y_{T_{1}})\leq R_{1}(Y_{T_{1}})=O(n^{4/3})$ ;
5.

$\hat{N}_{k}(T_{1},g_{2})=\Omega\left(g_{2}(n)^{3\cdot 2^{k-1}}\right)$ for all $k\geq 1$ such that $n^{2/3}g_{2}(n)^{-2^{k}}\rightarrow\infty$ .

Claim 5.6 implies there exists a coupling such that with $\Omega(1)$ probability

1.

$Z_{T_{2}}=O\left(\frac{n^{4/3}}{(\log\log n)^{12}}\right)$ ;
2.

$\lvert S(X_{T_{2}})\rvert\leq n^{2/3}r_{2}(n)\log_{a}\log\log n$ , $\lvert S(Y_{T_{2}})\rvert\leq n^{2/3}r_{2}(n)\log_{a}\log\log n$ ;
3.

$Q(Y_{T_{2}})=O(n^{4/3}r_{2}(n)\log_{a}\log\log n)$ , $Q(X_{T_{2}})=O(n^{4/3}r_{2}(n)\log_{a}\log\log n)$ ;
4.

$I(X_{T_{2}})=\Omega(n),I(Y_{T_{2}})=\Omega(n)$ ;
5.

$\hat{N}_{k}(T_{2},g_{3})=\Omega(g_{3}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{3}(n)^{-2^{k}}\rightarrow\infty$ .

Phase 3. Suppose the coupling in Phase 2 succeeds.

For Phase 3, we set the functions as $g_{3}(n)=\left(\log\log n\cdot\log\log\log n\right)^{2}$ , $g_{4}(n)=(\log n\cdot\log\log n)^{2}$ , $h_{3}(n)=\left(\log\log n\right)^{12}$ , $r_{3}(n)=20\log_{a}\log n\cdot\log\log_{a}\log n$ and $T_{3}=T_{2}+10\log_{a}\log n$ . Claim 5.6 implies there exists a coupling such that with $\Omega(1)$ probability

1.

$Z_{T_{3}}=O\left(\frac{n^{4/3}}{(\log n)^{10}}\right)$ ;
2.

$|S(X_{T_{3}})|=O(n^{2/3}r_{3}(n)\log_{a}\log n),|S(Y_{T_{3}})|=O(n^{2/3}r_{3}(n)\log_{a}\log n)$ ;
3.

$Q(X_{T_{3}})=O(n^{4/3}r_{3}(n)\log_{a}\log n)$ , $Q(Y_{T_{3}})=O(n^{2/3}r_{3}(n)\log_{a}\log n)$ ;
4.

$I(X_{T_{3}})=\Omega(n),I(Y_{T_{3}})=\Omega(n)$ ,
5.

$\hat{N}_{k}(T_{3},g_{4})=\Omega(g_{4}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g_{4}(n)^{-2^{k}}\rightarrow\infty$ .

Phase 4. Suppose the coupling in Phase 3 succeeds. Let $C_{2}$ be a constant greater than $4/3$ . We set $g_{4}(n)=\left(\log n\cdot\log\log n\right)^{2}$ , $h_{4}(n)=\left(\log n\right)^{10}$ , $r_{4}(n)=2C_{2}\log_{a}n\cdot\log\log_{a}n$ and $T_{4}=T_{3}+C_{2}\log_{a}n$ . Claim 5.6 implies there exists a coupling such that with $\Omega(1)$ probability $Z_{T_{4}}<1$ . Since $Z_{T_{4}}$ is a non-negative integer-value random variable, $\Pr[Z_{T_{4}}<1]=\Pr[Z_{T_{4}}=0]$ . When $Z_{T_{4}}=0$ , $X_{T_{4}}$ and $Y_{T_{4}}$ have the same component structure.

Therefore, if the coupling in every phase succeeds, $X_{T_{4}}$ and $Y_{T_{4}}$ have the same component structure. The probability that coupling in Phase 1 succeeds is $\left(\log\log\log n\right)^{-O(\log_{\varrho}(1/a_{1}))}$ . Conditional on the success of their previous phases, couplings in Phase 2, 3 and 4 succeed respectively with at least constant probability. Thus, the entire coupling succeeds with probability

\left(\log\log\log n\right)^{-O(\log_{\varrho}(1/a_{1}))}\cdot\Omega(1)\cdot\Omega(1)\cdot\Omega(1)=\left(\frac{1}{\log\log\log n}\right)^{\beta},

where $\beta$ is a positive constant. ∎

5.4.1 Proof of lemmas used in Section 5.4

Proof of Claim 5.6.

We will show that given the following properties at any time $t\leq T(n)$ , we can maintain them at time $t+1$ with probability at least $1-O(g(n)^{-1})-O(r(n)^{-1})$ :

1.

$Z_{t}=O\left(\frac{n^{4/3}}{h(n)}\right)$ ;
2.

$|S(X_{t})|,|S(Y_{t})|\leq C_{3}tn^{2/3}r(n)$ for a constant $C_{3}>0$ ;
3.

$Q(X_{t}),Q(Y_{t})\leq tn^{4/3}r(n)+O(n^{4/3})$ ;
4.

$I(X_{t}),I(Y_{t})=\Omega(n)$ ;
5.

$\hat{N}_{k}(t,g)=\Omega(g(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g(n)^{-2^{k}}\rightarrow\infty$ .

By assumption, $t\leq T(n)\leq r(n)/\log r(n)$ . According to Lemma 5.3, $X_{t+1}$ and $Y_{t+1}$ retain properties 2 and 3 with probability at least $1-O(r(n)^{-1})$ .

Given properties 1, 4 and 5, Lemma 5.5 (with $\eta=\log g(n)/2$ ) implies that there exist a constant $\delta>0$ and a coupling for the activation sub-step of $X_{t}$ and $Y_{t}$

	$\displaystyle\Pr\left[A(X_{t})=A(Y_{t})\right]$	$\displaystyle\geq 1-4e^{-\log g(n)}-\sqrt{\frac{g(n)\log g(n)}{2h(n)}}-\frac{\delta}{g(n)}$
		$\displaystyle=1-O\left(\frac{1}{h(n)^{1/3}}\right)-O\left(\frac{1}{g(n)}\right)=1-O\left(\frac{1}{g(n)}\right).$

Note that condition $g(n)\log g(n)\leq h(n)^{1/3}$ is used to deduce the inequality above. Suppose $A(X_{t})=A(Y_{t})$ ; we couple components generated in the percolation step and preclude the growth of $Z_{t}$ . Hence, $Z_{t+1}\leq Z_{t}=O\left(\frac{n^{4/3}}{h(n)}\right)$ , and property 1 holds immediately.

Recall that $\mathcal{R}_{1}(X)=Q(X)+\lvert S(X)\rvert^{2}$ . Properties 2 and 3 imply that $\mathcal{R}_{1}(X_{t})=O(t^{2}n^{4/3}r(n)^{2})$ and $\mathcal{R}_{1}(Y_{t})=O(t^{2}n^{4/3}r(n)^{2})$ . Since $t<T(n)$ and $T(n)^{2}\cdot r(n)^{2}\leq g(n)^{2}/\log g(n)$ , we can upper bound $\mathcal{R}_{1}(X_{t})$ and $\mathcal{R}_{1}(Y_{t})$ by

O\left(n^{4/3}\left(T(n)\cdot r(n)\right)^{2}\right)=O\left(\frac{n^{4/3}g(n)^{2}}{\log g(n)}\right).

We establish properties 4 and 5 with a similar argument as the one used in Phase 1.

Let $H_{t}\sim G(A(X_{t}),n/q)$ . Due to Lemma 5.4 (with $f=g$ ) and Corollary 3.12 with probability at least $1-O(g(n)^{-1})$ , $N_{k}(H_{t},g)=\Omega(g(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g(n)^{-2^{k}}\rightarrow\infty$ . In addition, $I(H_{t})=\Omega(n)$ with probability $1-O(n^{-1})$ by Lemma 3.2. Since the coupling adds components in $H_{t}$ to both $X_{t+1}$ and $Y_{t+1}$ , properties 4 and 5 are maintained at time $t+1$ , with probability at least $1-O(g(n)^{-1})$ .

A union bound concludes that at time $t+1$ we can maintain all five properties with probability at least $1-O(g(n)^{-1})-O(r(n)^{-1})$ . Hence, the probability that $X_{T(n)}$ and $Y_{T(n)}$ still satisfy the listed 5 properties above is

\left[1-O\left(\frac{1}{g(n)}\right)-O\left(\frac{1}{r(n)}\right)\right]^{T(n)}=1-o(1).

It remains for us to show the bound for $Z_{T}$ and that for a given function $g^{\prime}$ satisfying $g^{\prime}\geq g$ and $g^{\prime}(n)=o(n^{1/3})$ , then $\hat{N}_{k}(T,g^{\prime})=\Omega\left(g^{\prime}(n)^{3\cdot 2^{k-1}}\right)$ for all $k\geq 1$ such that $n^{2/3}g^{\prime}(n)^{-2^{k}}\rightarrow\infty$ .

Conditioned on $A(X_{t})=A(Y_{t})$ for every activation sub-step in this phase, a bound for $Z_{T}$ can be obtained through a first moment method. On expectation $Z_{t}$ contract by a factor of $\frac{1}{a}=1-\frac{1}{q}$ each step. Thus, we can recursively compute the expectation of $\operatorname*{{\rm E}}[Z_{T}]$ :

\displaystyle\operatorname*{{\rm E}}[Z_{T}]

\displaystyle=\operatorname*{{\rm E}}[\operatorname*{{\rm E}}[Z_{T}\mid Z_{T-1}]]=\frac{1}{a}\cdot\operatorname*{{\rm E}}[Z_{T-1}]=...=\left(\frac{1}{a}\right)^{T}\operatorname*{{\rm E}}[Z_{0}]=O\left(\left(\frac{1}{a}\right)^{T}\cdot\frac{n^{4/3}}{h(n)}\right).

(13)

It follows from Markov’s inequality that with at least constant probability

Z_{T}=O\left(\frac{n^{4/3}}{a^{T(n)}}\right).

Finally, in the last percolation step in this phase, Corollary 3.12 guarantees that with high probability $\hat{N}_{k}(T,g^{\prime})$ $=\Omega(g^{\prime}(n)^{3\cdot 2^{k-1}})$ for all $k\geq 1$ such that $n^{2/3}g^{\prime}(n)^{-2^{k}}\rightarrow\infty$ . The claim follows from a union bound. ∎

Proof of Lemma 5.3.

We establish first the bound for $|S(X_{t+1})|$ . Suppose $s$ vertices are activated from $S(X_{t})$ . By assumption

Q(X_{t})\leq tn^{4/3}r(n)+O(n^{4/3})\leq\frac{2n^{4/3}r(n)^{2}}{\log r(n)},

for sufficiently large $n$ . Hence, Hoeffding’s inequality implies that

A(X_{t})\leq s+\frac{n-|S(X_{t})|}{q}+n^{2/3}r(n)\leq\frac{n}{q}+\frac{(q-1)s}{q}+n^{2/3}r(n),

with probability at least $1-O(r(n)^{-1})$ .

We consider two cases. First suppose that $\delta(q-1)s/q\geq n^{2/3}r(n)$ , where $\delta>0$ is a sufficiently small constant we choose later. Then,

A(X_{t})\leq\frac{n}{q}+\frac{(1+\delta)(q-1)s}{q}=:M.

The largest new component corresponds to the largest component of a $G(A(X_{t}),q/n)$ random graph. Let $N$ be the size of that component, and let $N_{M}$ be the size of the largest component of a $G\left(M,\frac{1+\varepsilon}{M}\right)$ random graph, where $\varepsilon=qM/n-1$ . By Fact 3.1, $N$ is stochastically dominated by $N_{M}$ . Then by Corollary 3.6 there exists a constant $c>0$ such that

\Pr\left[N>(2+\rho)\varepsilon M\right]\leq\Pr[N_{M}>(2+\rho)\varepsilon M]=O({\operatorname*{{\rm e}}}^{-c\varepsilon^{3}M}),

(14)

for any $\rho<1/10$ . Now,

$\displaystyle\varepsilon M$	$\displaystyle=\frac{(1+\delta)(q-1)s}{n}\left(\frac{n}{q}+\frac{(1+\delta)(q-1)s}{q}\right)$
	$\displaystyle=\frac{(1+\delta)(q-1)s}{q}+O\left(\frac{s^{2}}{n}\right)$
	$\displaystyle\leq\frac{(1+\delta)(q-1)s}{q}+O(n^{1/3}r(n)^{4}),$
	$\displaystyle\leq\frac{(1+2\delta)(q-1)s}{q},$	(15)

where for the second to last inequality we use that $s\leq|S(X_{t})|=O(n^{2/3}r(n)^{2})$ , and the last inequality follows from the assumptions $\frac{\delta(q-1)s}{q}\geq n^{2/3}r(n)$ and $r(n)=o\left(n^{1/15}\right)$ . Also, since $s=O(n^{2/3}r(n)^{2})$ and $r(n)=o\left(n^{1/15}\right)$ ,

\displaystyle\varepsilon^{3}M=\left[\frac{(1+\delta)(q-1)s}{n}\right]^{3}\left(\frac{n}{q}+\frac{(1+\delta)(q-1)s}{q}\right)=\Omega\left(\frac{s^{3}}{n^{2}}+\frac{s^{4}}{n^{3}}\right)=\Omega(r(n)^{3}).

(16)

Hence, (14), (15) and (16) imply

\Pr\left[N\geq\frac{(2+\rho)(1+2\delta)(q-1)s}{q}\right]={\operatorname*{{\rm e}}}^{-\Omega(r(n)^{3})}.

Since $q<2$ , for sufficiently small $\rho$ and $\delta$

\frac{(2+\rho)(1+2\delta)(q-1)}{q}<1.

Therefore, $N\leq s$ with probability $1-\exp(-\Omega(r(n)^{3}))$ . If this is the case, then $|S(X_{t+1})|\leq|S(X_{t})|$ and so by a union bound $|S(X_{t+1})|\leq c(t+1)n^{2/3}r(n)$ with probability at least $1-O(r(n)^{-1})$ .

For the second case we assume $\frac{\delta(q-1)s}{q}<n^{2/3}r(n)$ and proceed in similar fashion. In this case, Hoeffding’s inequality implies with probability at least $1-O(r(n)^{-1})$ ,

A(X_{t})\leq\frac{n}{q}+(1+1/\delta)n^{2/3}r(n)=:M^{\prime}.

The size of the largest new component, denoted $N^{\prime}$ , is stochastically dominated by the size of the largest component of a $G(M^{\prime},\frac{1+\varepsilon^{\prime}}{M^{\prime}})$ random graph, with $\varepsilon^{\prime}=qM^{\prime}/n-1$ . Now, since we assume $r(n)=o\left(n^{1/15}\right)$ ,

	$\displaystyle\varepsilon^{\prime}M^{\prime}$	$\displaystyle\leq\frac{q(1+1/\delta)r(n)}{n^{1/3}}\left[\frac{n}{q}+(1+1/\delta)n^{2/3}r(n)\right]$
		$\displaystyle=(1+1/\delta)n^{2/3}r(n)+O(n^{1/3}r(n)^{2})\leq\frac{c}{3}n^{2/3}r(n),$

where the last inequality holds for large $n$ and a sufficiently large constant $c$ . Moreover,

\displaystyle\left({\varepsilon^{\prime}}\right)^{3}M^{\prime}=\Omega\left(\frac{r(n)^{3}}{n}\left[\frac{n}{q}+n^{2/3}r(n)\right]\right)=\Omega(r(n)^{3}).

Hence,

\Pr\left[N^{\prime}\geq cn^{2/3}r(n)\right]\leq\Pr\left[N^{\prime}\geq\frac{(2+\rho)cn^{2/3}r(n)}{3}\right]\leq\Pr\left[N^{\prime}\geq(2+\rho)\varepsilon^{\prime}M^{\prime}\right],

where $\rho<1/10$ , and by Corollary 3.6

\displaystyle\Pr\left[N^{\prime}\geq(2+\rho)\varepsilon^{\prime}M^{\prime}\right]={\operatorname*{{\rm e}}}^{-\Omega(\left({\varepsilon^{\prime}}\right)^{3}M^{\prime})}={\operatorname*{{\rm e}}}^{-\Omega(r(n)^{3})}.

Since, $|S(X_{t+1})|\leq|S(X_{t})|+N^{\prime}$ , a union bound implies that $|S(X_{t+1})|\leq c(t+1)n^{2/3}r(n)$ with probability at least $1-O(r(n)^{-1})$ as desired.

Finally, to bound $Q(X_{t+1})$ we observe that if $C_{1},\dots,C_{k}$ are all the new components in order of their sizes, then by Lemma 3.4 and Markov’s inequality:

\Pr\left[\sum_{j\geq 2}|C_{j}|^{2}\geq n^{4/3}r(n)\right]=O(r(n)^{-1}).

Thus, $Q(X_{t+1})\leq Q(X_{t})+n^{4/3}r(n)\leq(t+1)n^{4/3}r(n)$ with probability at least $1-O(r(n)^{-1})$ as claimed. The lemma follows from a union bound. ∎

Proof of Lemma 5.4.

Since $\mathcal{R}_{1}(X_{t})=O\left(n^{4/3}f(n)^{2}(\log f(n))^{-1}\right)$ , by Hoeffding’s inequality

A(X_{t})\in\left[\frac{n-n^{2/3}f(n)}{q},\frac{n+n^{2/3}f(n)}{q}\right]=:J,

with probability at least $1-O(f(n)^{-1})$ . The new connected components in $X_{t+1}$ correspond to those of a $G(A(X_{t}),\frac{1+\varepsilon}{A(X_{t})})$ random graph, where $\varepsilon=A(X_{t})q/n-1$ . If $A(X_{t})\in J$ , then

-n^{-1/3}f(n)\leq\varepsilon\leq n^{-1/3}f(n).

(17)

Since $A(X_{t})\in J$ we can also define $m:=A(X_{t})=\theta n$ for $\theta\in(1/2q,1)$ , and $\lambda:=\varepsilon m^{1/3}$ , so we may rewrite (17) as

-f(n)\leq-\theta^{1/3}f(n)\leq\lambda\leq\theta^{1/3}f(n)\leq f(n),

and the lemma follows. ∎

An important tool used in the proof of Lemma 5.5 is the following coupling on a (lazy) symmetric random walk on $\mathbb{Z}$ ; its proof is given in Appendix B.

Theorem 5.7.

Let $A>0$ and let $A\leq c_{1},c_{2},\dots,c_{m}\leq 2A$ be positive integers. Let $r\in(0,1/2]$ and consider the sequences of random variables $X_{1},\dots,X_{m}$ and $Y_{1},\dots,Y_{m}$ where for each $i=1,\dots,m$ : $X_{i}=c_{i}$ with probability $r$ ; $X_{i}=-c_{i}$ with probability $r$ ; $X_{i}=0$ otherwise and $Y_{i}$ has the same distribution as $X_{i}$ . Let $X=\sum_{i=1}^{m}X_{i}$ and $Y=\sum_{i=1}^{m}Y_{i}$ . Then for any $d>0$ , there exist a constant $\delta:=\delta(r)>0$ and a coupling of $X$ and $Y$ such that

\Pr[d+2A\geq X-Y\geq d]\geq 1-\frac{\delta(d+A)}{A\sqrt{m}}.

We note that Theorem 5.7 is a generalization of the following more standard fact which will also be useful to us.

Lemma 5.8 ([4], Lemma 2.18).

Let $X$ and $Y$ be binomial random variables with parameters $m$ and $r$ , where $r\in(0,1)$ is a constant. Then, for any integer $y>0$ , there exists a coupling $(X,Y)$ such that for a suitable constant $\gamma=\gamma(r)>0$ ,

\Pr[X-Y=y]\geq 1-\frac{\gamma y}{\sqrt{m}}.

Proof of Lemma 5.5.

For ease of notation let $\mathcal{I}_{k}=\mathcal{I}_{k}(g)$ and $\hat{N}_{k}=\hat{N}_{k}(t,g)$ for each $k\geq 1$ . Also recall the notations $W_{t}$ , $M(X)$ and $D(X)$ defined in Section 2.2. Let $\hat{I}(X_{t})$ and $\hat{I}(Y_{t})$ be the isolated vertices in $W_{t}$ from $X_{t}$ and $Y_{t}$ , respectively.

Let $k^{*}:=\min_{k}\{k\in\mathbb{Z}:g(n)^{2^{k}}\geq\vartheta n^{1/3}\}$ . The activation of the non-trivial components in $M(X_{t})$ and $M(Y_{t})$ whose sizes are not in $\{1\}\cup\mathcal{I}_{1}\cup\dots\cup\mathcal{I}_{k^{*}}$ is coupled using the matching $W_{t}$ . That is, $c\in M(X_{t})$ and $W_{t}(c)\in M(Y_{t})$ are activated simultaneously with probability $1/q$ . The components in $D(X_{t})$ and $D(Y_{t})$ are activated independently. After independently activating these components, the number of active vertices from each copy is not necessarily the same. The idea is to couple the activation of the remaining components in $M(X_{t})$ and $M(Y_{t})$ in way that corrects this difference.

Let $A_{0}(X_{t})$ and $A_{0}(Y_{t})$ be number of active vertices from $X_{t}$ and $Y_{t}$ , respectively, after the activation of the components from $D(X_{t})$ and $D(Y_{t})$ . Observe that $\operatorname*{{\rm E}}[A_{0}(X_{t})]=\operatorname*{{\rm E}}[A_{0}(Y_{t})]=:\mu$ and that by Hoeffding’s inequality, for any $\eta(n)>0$

\Pr\left[\lvert A_{0}(X_{t})-\mu\rvert\geq\sqrt{\eta(n)Z_{t}}\right]\leq 2e^{-2\eta(n)}.

Recall $Z_{t}\leq\frac{Cn^{4/3}}{h(n)}$ . Hence, with probability at least $1-4\exp\left(-2\eta(n)\right)$ ,

d_{0}:=\left|A_{0}(X_{t})-A_{0}(Y_{t})\right|\leq 2\sqrt{\eta(n)Z_{t}}\leq\frac{2{\sqrt{C\eta(n)}n^{2/3}}}{\sqrt{h(n)}}.

We first couple the activation of the components in $\mathcal{I}_{1}$ , then in $\mathcal{I}_{2}$ and so on up to $\mathcal{I}_{k^{*}}$ . Without loss of generality, suppose that $d_{0}=A_{0}(Y_{t})-A_{0}(X_{t})$ . If $d_{0}\leq\frac{\vartheta n^{2/3}}{g(n)^{2}}$ , we simply couple the components with sizes in $\mathcal{I}_{1}$ using the matching $W_{t}$ . Suppose otherwise that $d_{0}>\frac{\vartheta n^{2/3}}{g(n)^{2}}$ . Let $A_{1}(X_{t})$ and $A_{1}(Y_{t})$ be random variables corresponding to the numbers of active vertices from $M(X_{t})$ and $M(Y_{t})$ with sizes in $\mathcal{I}_{1}$ respectively. By assumption $\hat{N}_{1}\geq bg(n)^{3}$ . Hence, Theorem 5.7 implies that for $\delta=\delta(q)>0$ , there exists a coupling for the activation of the components in $M(X_{t})$ and $M(Y_{t})$ with sizes in $\mathcal{I}_{1}$ such that

d_{0}\geq A_{1}(X_{t})-A_{1}(Y_{t})\geq d_{0}-\frac{\vartheta n^{2/3}}{g(n)^{2}}

with probability at least

1-\frac{\delta\left(d_{0}-\frac{\vartheta n^{2/3}}{2g(n)^{2}}\right)}{\frac{\vartheta n^{2/3}}{2g(n)^{2}}\sqrt{bg(n)^{3}}}\geq 1-\frac{\delta d_{0}}{\frac{\vartheta n^{2/3}}{2g(n)^{2}}\sqrt{bg(n)^{3}}}\geq 1-\frac{4\delta\sqrt{C\eta(n)g(n)}}{\vartheta\sqrt{bh(n)}}\geq 1-\sqrt{\frac{\eta(n)g(n)}{h(n)}},

where the last inequality holds for $\vartheta$ large enough. Let $d_{1}:=\left(A_{0}(Y_{t})-A_{0}(X_{t})\right)+\left(A_{1}(Y_{t})-A_{1}(X_{t})\right)$ . If the coupling succeeds, we have $0\leq d_{1}\leq\frac{\vartheta n^{2/3}}{g(n)^{2}}$ . Thus, we have shown that $d_{1}\leq\frac{\vartheta n^{2/3}}{g(n)^{2}}$ with probability at least

\left(1-4e^{-2\eta(n)}\right)\left(1-\sqrt{\frac{\eta(n)g(n)}{h(n)}}\right)\geq 1-4e^{-2\eta(n)}-\sqrt{\frac{\eta(n)g(n)}{h(n)}}.

Now, let $d_{k}$ be the difference in the number of active vertices after activating the components in $\mathcal{I}_{k}$ . Suppose that $d_{k}\leq\frac{\vartheta n^{2/3}}{g(n)^{2^{k}}}$ , for $k\leq k^{*}$ . By assumption, $\hat{N}_{k+1}\geq bg(n)^{3\cdot 2^{k}}$ . Thus, using Theorem 5.7 again we get that there exists a coupling for the activation of the components in $\mathcal{I}_{k+1}$ such that

\Pr\left[d_{k+1}\leq\frac{\vartheta n^{2/3}}{g(n)^{2^{k+1}}}\,\middle|\,d_{k}\leq\frac{\vartheta n^{2/3}}{g(n)^{2^{k}}}\right]\geq 1-\frac{\delta d_{k}}{\frac{\vartheta n^{2/3}}{2g(n)^{2^{k+1}}}\sqrt{bg(n)^{3\cdot 2^{k}}}}\geq 1-\frac{2\delta}{\sqrt{b}g(n)^{2^{k-1}}}.

Therefore, there is a coupling of the activation components in $\mathcal{I}_{2},\mathcal{I}_{3},\dots,\mathcal{I}_{k^{*}}$ such that

\Pr\left[d_{k^{*}}\leq n^{1/3}\,\middle|\,d_{1}\leq\frac{\vartheta n^{2/3}}{g(n)^{2}}\right]\geq\prod_{k=2}^{k^{*}}\left(1-\frac{\delta^{\prime}}{g(n)^{2^{k-1}}}\right),

where $\delta^{\prime}=2\delta/\sqrt{b}$ . Note that for a suitable constant $\delta^{\prime\prime}>0$ , we have

\prod_{k\geq 2}^{k^{*}}\left(1-\frac{\delta^{\prime}}{g(n)^{2^{k-1}}}\right)=\exp\left(\sum_{k\geq 1}^{k^{*}}\ln\left(1-\frac{\delta^{\prime}}{g(n)^{2^{k}}}\right)\right)\geq\exp\left(-\delta^{\prime\prime}\sum_{k\geq 1}^{k^{*}}\frac{1}{g(n)^{2^{k}}}\right),

and since

\sum_{k\geq 1}^{k^{*}}\frac{1}{g(n)^{2^{k}}}\leq\sum_{k\geq 1}^{\infty}\frac{1}{g(n)^{2^{k}}}\leq\sum_{k\geq 1}^{\infty}\frac{1}{g(n)^{{k}}}\leq\frac{1}{g(n)^{2}-g(n)},

we get

\prod_{k=2}^{k^{*}}\left(1-\frac{\delta^{\prime}}{g(n)^{2^{k-1}}}\right)\geq\exp\left(-\frac{\delta^{\prime\prime}}{g(n)^{2}-g(n)}\right)\geq 1-\frac{\delta^{\prime\prime}}{g(n)^{2}-g(n)}.

Finally, we couple $\hat{I}(X_{t})$ and $\hat{I}(Y_{t})$ to fix $d_{k^{*}}$ . By assumption $I(X_{t}),I(Y_{t})=\Omega(n)$ , so $m:=|\hat{I}(X_{t})|=|\hat{I}(Y_{t})|=\Omega(n)$ . Let $A_{I}(X_{t})$ and $A_{I}(Y_{t})$ denote the total number of activated isolated vertices from $\hat{I}(X_{t})$ and $\hat{I}(Y_{t})$ respectively. We activate all isolated vertices independently, so $A_{I}(X_{t})$ and $A_{I}(Y_{t})$ can be seen as two binomial random variables with the same parameters $m$ and $1/q$ . Lemma 5.8 gives a coupling for binomial random variables such that for $r\leq n^{1/3}$ ,

\Pr\left[A_{I}(X_{t})-A_{I}(Y_{t})=r\right]\geq 1-O\left(\frac{1}{n^{1/6}}\right)=1-o\left(\frac{1}{g(n)}\right).

Therefore,

\Pr\left[A(X_{t})=A(Y_{t})\right]\geq 1-4e^{-2\eta(n)}-\sqrt{\frac{\eta(n)g(n)}{h(n)}}-O\left(\frac{1}{g(n)}\right),

as claimed. ∎

6 New mixing time for the Glauber dynamics via comparison

In this section, we establish a comparison inequality between the mixing times of the CM dynamics and of the heat-bath Glauber dynamics for the random-cluster model for a general graph $G=(V,E)$ . The Glauber dynamics is defined as follows. Given a random-cluster configuration $A_{t}$ , one step of this chain is given by:

(i)

pick an edge $e\in E$ uniformly at random;
(ii)

replace the current configuration $A_{t}$ by $A_{t}\cup\{e\}$ with probability

$\frac{\mu_{G,p,q}(A_{t}\cup\{e\})}{\mu_{G,p,q}(A_{t}\cup\{e\})+\mu_{G,p,q}(A_{t}\setminus\{e\})};$
(iii)

else replace $A_{t}$ by $A_{t}\setminus\{e\}$ .

It is immediate from its definition this chain is reversible with respect to $\mu=\mu_{G,p,q}$ and thus converges to it.

The following comparison inequality was proved in [7]:

\mathrm{gap}^{-1}(\mathrm{GD})\leq O(m\log m)\cdot\mathrm{gap}^{-1}(\mathrm{CM}),

(18)

where $m$ denotes the number of edges in $G$ , and $\mathrm{gap}(\mathrm{CM})$ , $\mathrm{gap}(\mathrm{GD})$ the spectral gaps of the transition matrices of the CM and Glauber dynamics, respectively. The standard connection between the spectral gap and the mixing time (see, e.g., Theorem 12.3 in [23]) yields

\tau_{\rm mix}^{\mathrm{GD}}\leq O(m\log m)\cdot\tau_{\rm mix}^{\mathrm{CM}}\cdot\log\mu_{\mathrm{min}}^{-1},

(19)

where $\mu_{\mathrm{min}}=\min_{A\in\Omega}\mu(A)$ with $\Omega$ denoting the set of random-cluster configurations on $G$ . In some cases, such as in the mean-field model with $p=\Theta(n^{-1})$ , $\log\mu_{\mathrm{min}}^{-1}=\Omega(m\log m)$ , and a factor of $O(m^{2}(\log m)^{2})$ is thus lost in the comparison. We provide here an improved version of this inequality.

Theorem 6.1.

For any $q>1$ and any $p\in(0,1)$ , the mixing time of Glauber dynamics for the random-cluster model on a graph $G$ with $n$ vertices and $m$ edges satisfies

\tau_{\rm mix}^{\mathrm{GD}}\leq O\left(mn\log n+pm^{2}\log n\cdot\log\frac{1}{\min\{p,1-p\}}\right)\cdot\tau_{\rm mix}^{\mathrm{CM}}.

We note that in the mean-field model, where $m=\Theta(n^{2})$ and we take $p=\zeta/n$ with $\zeta=O(1)$ , this theorem yields that $\tau_{\rm mix}^{\mathrm{GD}}=O(n^{3}(\log n)^{2})\cdot\tau_{\rm mix}^{\mathrm{CM}}$ , which establishes Theorem 1.2 from the introduction and improves by a factor of $O(n)$ the best previously known bound for the Glauber dynamics on the complete graph.

To prove Theorem 6.1 we use the following standard fact.

Theorem 6.2.

Let $P$ be a Markov chain on state space $\Gamma$ with stationary distribution $\pi$ . Suppose there exist a subset of states $\Gamma_{0}\subseteq\Gamma$ and a time $T$ , such that for any $t\geq T$ and any $x\in\Gamma$ we have $P^{t}(x,\Gamma\setminus\Gamma_{0})\leq\frac{1}{16}.$ Then

\tau_{\rm mix}^{P}=O\left(T+\mathrm{gap}^{-1}(P)\log(8\pi_{0}^{-1})\right),

(20)

where $\pi_{0}:=\min_{\omega\in\Gamma_{0}}\pi(\omega)$ .

Note that $\pi_{0}$ is the minimum probability of any configuration on $\Gamma_{0}$ . Without the additional assumptions in the theorem, the best possible bound involves a factor of $\pi_{\mathrm{min}}=\min_{A\in\Gamma}\pi(A)$ instead. We remark that there are related conditions under which (20) holds; we choose the condition that $P^{t}(x,\Gamma\setminus\Gamma_{0})\leq\frac{1}{16}$ for every $x$ and every $t\geq T$ for convenience.

We can now provide the proof of Theorem 6.1.

Proof of Theorem 6.1.

First note that if $p=\Omega(1)$ , it suffices to prove that

\tau_{\rm mix}^{\mathrm{GD}}=O\left(mn\log n+m^{2}\log n\log\frac{1}{\min\{p,1-p\}}\right)\cdot\tau_{\rm mix}^{\mathrm{CM}}.

This follows from (19) and the fact that

\mu_{\mathrm{min}}\geq\frac{\min\{p,1-p\}^{m}}{q^{n-1}}

since the partition function for the random-cluster model on $G$ satisfies $Z_{G}\leq q^{n}$ (see, e.g., Theorem 3.60 in [19]).

Thus, we may assume $p\leq 1/100$ . From (18) and the standard relationship between the spectral gap and the mixing time (see, e.g., Theorem 12.4 in [23]) we obtain:

\mathrm{gap}^{-1}(\mathrm{GD})\leq\tau_{\rm mix}^{\mathrm{CM}}\cdot O(m\log n).

(21)

Let $P$ denote the transition matrix of the Glauber dynamics. In order to apply Theorem 6.2, we have to find a suitable subset of states $\Omega_{0}\subseteq\Omega$ and a suitable time $T$ so that $P^{t}(A,\Omega\setminus\Omega_{0})\leq\frac{1}{16}$ , for every $A\in\Omega$ and every $t\geq T$ .

We let $\Omega_{0}=\{A\subseteq E:|A|\leq 100mp\}$ and $T=Cm\log m$ for a sufficiently large constant $C>0$ . When an edge is selected for update by the Glauber dynamics, it is set to be open with probability $p/(p+q(1-p))$ if it is a “cut edge” or with probability $p$ if it is not; recall that we say an edge $e$ is open if the edge is present in the random-cluster configuration. Therefore, since $p\geq p/(p+q(1-p))$ when $q>1$ , after every edge has been updated at least once the number of open edges in any configuration is stochastically dominated by the number of edges in a $G(n,p)$ random graph. By the coupon collector bound, every edge has been updated at least once at time $T$ w.h.p. for large enough $C$ . Moreover, if all edges are indeed updated by time $T$ , the number of open edges in $X_{t}$ at any time $t\geq T$ is at most $100mp$ with probability at least $19/20$ by Markov’s inequality. Therefore, the Glauber dynamics satisfies condition in Theorem 6.2 for these choices of $T$ and $\Omega_{0}$ .

It remains for us to estimate $\pi_{0}$ . Let $\pi_{m}$ denote the probability of the configuration where all the edges are open; then,

\pi_{m}=\frac{p^{m}q}{Z_{G}}\geq\frac{p^{m}}{q^{n-1}},

(22)

where the inequality follows from the fact that $Z_{G}\leq q^{n}$ . Moreover, since $1-p>p$ when $p\leq 1/100$ , then $\pi_{0}\geq qp^{100mp}(1-p)^{m-100mp}/Z_{G}$ and so

\frac{\pi_{0}}{\pi_{m}}\geq\frac{qp^{100mp}(1-p)^{m-100mp}}{p^{m}q}=\left(\frac{1-p}{p}\right)^{m-100mp}.

(23)

Using (22), (23) and the fact that $p\leq 1/100$ , we obtain:

	$\displaystyle\log\frac{1}{\pi_{0}}$	$\displaystyle=\log\frac{1}{\pi_{m}}+\log\frac{\pi_{m}}{\pi_{0}}\leq(n-1)\log q+m\log p^{-1}-(m-100mp)\log\frac{1-p}{p}$
		$\displaystyle=100mp\log p^{-1}+m(1-100p)\log\frac{1}{1-p}+O(n)$
		$\displaystyle\leq 100mp\log p^{-1}+\frac{mp(1-100p)}{1-p}+O(n)=O(n+mp(\log p^{-1})).$

Therefore, from (21) and Theorem 6.2 we obtain:

\tau_{\rm mix}^{\mathrm{GD}}\leq O(m\log m)+\tau_{\rm mix}^{\mathrm{CM}}\cdot O(m\log n)\cdot O(n+mp(\log p^{-1}))=O(m\log n\cdot(n+mp\log p^{-1}))\cdot\tau_{\rm mix}^{\mathrm{CM}},

as claimed. ∎

For the sake of completeness, we conclude this section with a proof of Theorem 6.2.

Proof of Theorem 6.2.

For $x\in\Gamma$ and $t\geq T$ , we have

	$\displaystyle{\\|P^{t}(x,\cdot)-\pi(\cdot)\\|}_{\textsc{\tiny TV}}$	$\displaystyle=\sum_{y\in\Gamma:P^{t}(x,y)>\pi(y)}P^{t}(x,y)-\pi(y)$
		$\displaystyle\leq\sum_{y\in\Gamma_{0}:P^{t}(x,y)>\pi(y)}\pi(y)\left\|1-\frac{P^{t}(x,y)}{\pi(y)}\right\|+\sum_{y\notin\Gamma_{0}:P^{t}(x,y)>\pi(y)}P^{t}(x,y)\left\|1-\frac{\pi(y)}{P^{t}(x,y)}\right\|$
		$\displaystyle\leq\pi(\Gamma_{0})\max_{y\in\Gamma_{0}}\left\|1-\frac{P^{t}(x,y)}{\pi(y)}\right\|+P^{t}(x,\Gamma\setminus\Gamma_{0})$
		$\displaystyle\leq\max_{y\in\Gamma_{0}}\left\|1-\frac{P^{t}(x,y)}{\pi(y)}\right\|+\frac{1}{16},$

where the last inequality follows from the theorem assumption for $t\geq T$ .

For any $y\in\Gamma$ , we have

\left|1-\frac{P^{t}(x,y)}{\pi(y)}\right|\leq\frac{e^{-\mathrm{gap}(P)\cdot t}}{\sqrt{\pi(x)\pi(y)}};

see inequality (12.11) in [23]. Hence, for any $x\in\Gamma_{0}$ we have

{\|P^{t}(x,\cdot)-\pi(\cdot)\|}_{\textsc{\tiny TV}}\leq\max_{y\in\Gamma_{0}}\frac{e^{-\mathrm{gap}(P)\cdot t}}{\sqrt{\pi(x)\pi(y)}}+\frac{1}{16}\leq\frac{e^{-\mathrm{gap}(P)\cdot t}}{\pi_{0}}+\frac{1}{16}.

(24)

Letting $\tau_{\rm mix}^{P}(x)=\min\left\{{t\geq 0:\|P^{t}(x,\cdot)-\pi(\cdot)\|}_{\textsc{\tiny TV}}\leq 1/4\right\}$ , we deduce from (24) that for $x\in\Gamma_{0}$

\tau_{\rm mix}^{P}(x)\leq\max\left\{T,\mathrm{gap}^{-1}(P)\log\frac{8}{\pi_{0}}\right\}.

(25)

Since $\tau_{\rm mix}^{P}=\max_{x\in\Gamma}\tau_{\rm mix}(x)$ , it remains for us to provide a bound for $\tau_{\rm mix}(x)$ when $x\in\Gamma\setminus\Gamma_{0}$ . Consider two copies $\{X_{t}\}$ , $\{Y_{t}\}$ of the chain $P$ . For $t>T$ let $\mathbb{P}$ be the coupling of $X_{t}$ , $Y_{t}$ such that the two copies evolve independently up to time $T$ and if $X_{T}=x^{\prime}$ and $Y_{T}=y^{\prime}$ for some $x^{\prime},y^{\prime}\in\Gamma_{0}$ then the optimal coupling is used so that

\mathbb{P}[X_{t}\neq Y_{t}\mid X_{T}=x^{\prime},Y_{T}=y^{\prime}]={\|P^{t-T}(x^{\prime},\cdot)-P^{t-T}(y^{\prime},\cdot)\|}_{\textsc{\tiny TV}};

recall that the existence of an optimal coupling is guaranteed by the coupling lemma (see, e.g., Proposition 4.7 in [23]). Then, for any $x,y\in\Gamma$

	$\displaystyle\mathbb{P}[X_{t}\neq Y_{t}$	$\displaystyle\mid X_{0}=x,Y_{0}=y]$
		$\displaystyle\leq\mathbb{P}[X_{T}\notin\Gamma_{0}\mid X_{0}=x]+\mathbb{P}[Y_{T}\notin\Gamma_{0}\mid Y_{0}=y]+\max_{x^{\prime},y^{\prime}\in\Gamma_{0}}\mathbb{P}[X_{t}\neq Y_{t}\mid X_{T}=x^{\prime},Y_{T}=y^{\prime}]$
		$\displaystyle\leq\max_{x^{\prime},y^{\prime}\in\Gamma_{0}}\mathbb{P}[X_{t}\neq Y_{t}\mid X_{T}=x^{\prime},Y_{T}=y^{\prime}]+\frac{1}{8}$
		$\displaystyle\leq\max_{x^{\prime},y^{\prime}\in\Gamma_{0}}{\\|P^{t-T}(x^{\prime},\cdot)-P^{t-T}(y^{\prime},\cdot)\\|}_{\textsc{\tiny TV}}+\frac{1}{8}$
		$\displaystyle\leq 2\max_{x^{\prime}\in\Gamma_{0}}{\\|P^{t-T}(x^{\prime},\cdot)-\pi(\cdot)\\|}_{\textsc{\tiny TV}}+\frac{1}{8},$

where the last inequality follows from the triangle inequality. Now,

\displaystyle\max_{x\in\Gamma}{\|P^{t}(x,\cdot)-\pi(\cdot)\|}_{\textsc{\tiny TV}}

\displaystyle\leq\max_{x,y\in\Gamma}\mathbb{P}[X_{t}\neq Y_{t}\mid X_{0}=x,Y_{0}=y]\leq 2\max_{x^{\prime}\in\Gamma_{0}}{\|P^{t-T}(x^{\prime},\cdot)-\pi(\cdot)\|}_{\textsc{\tiny TV}}+\frac{1}{8}\leq\frac{5}{8}.

provided $t\geq T+\max_{z\in\Gamma_{0}}\tau_{\rm mix}^{P}(z)$ . Using a standard boosting argument (see (4.36) in [23]) and (25) we deduce that $\tau_{\rm mix}^{P}=O(T+\mathrm{gap}^{-1}(P)\log\frac{8}{\pi_{0}})$ as claimed. ∎

References

[1] N. Alon and J.H. Spencer. The probabilistic method. John Wiley & Sons, 2000.
[2] V. Beffara and H. Duminil-Copin. The self-dual point of the two-dimensional random-cluster model is critical for $q\geq 1$ . Probability Theory and Related Fields, 153:511–542, 2012.
[3] A. C. Berry. The accuracy of the gaussian approximation to the sum of independent variates. 1941.
[4] A. Blanca. Random-cluster dynamics. PhD thesis, UC Berkeley, 2016.
[5] A. Blanca and R. Gheissari. Random-cluster dynamics on random regular graphs in tree uniqueness. Communications in Mathematical Physics, 2021.
[6] A. Blanca, R. Gheissari, and E. Vigoda. Random-cluster dynamics in $\mathbb{Z}^{2}$ : rapid mixing with general boundary conditions. Annals of Applied Probability, 30(1):418–459, 2020.
[7] A. Blanca and A. Sinclair. Dynamics for the mean-field random-cluster model. Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 528–543, 2015.
[8] A. Blanca and A. Sinclair. Random-Cluster Dynamics in $\mathbb{Z}^{2}$ . Probability Theory and Related Fields, 168:821–847, 2017.
[9] B. Bollobás, G.R. Grimmett, and S. Janson. The random-cluster model on the complete graph. Probability Theory and Related Fields, 104(3):283–317, 1996.
[10] L. Chayes and J. Machta. Graphical representations and cluster algorithms II. Physica A, 254:477–516, 1998.
[11] H. Duminil-Copin, M. Gagnebin, M. Harel, I. Manolescu, and V. Tassion. Discontinuity of the phase transition for the planar random-cluster and Potts models with $q>4$ . Annales de l’ENS, 2016. To Appear.
[12] H. Duminil-Copin, V. Sidoravicius, and V. Tassion. Continuity of the Phase Transition for Planar Random-Cluster and Potts Models with $1\!\leq\!q\!\leq\!4$ . Communications in Mathematical Physics, 349(1):47–107, 2017.
[13] R. Durrett. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2010.
[14] C.M. Fortuin and P.W. Kasteleyn. On the random-cluster model I. Introduction and relation to other models. Physica, 57(4):536–564, 1972.
[15] A. Galanis, D. Štefankovič, and E. Vigoda. Swendsen-Wang algorithm on the mean-field Potts model. Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 815–828, 2015.
[16] T. Garoni. Personal communication, 2015.
[17] R. Gheissari and E. Lubetzky. Quasi-polynomial mixing of critical two-dimensional random cluster models. Random Structures & Algorithms, 56(2):517–556, 2020.
[18] R. Gheissari, E. Lubetzky, and Y. Peres. Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1981–1988. SIAM, 2018.
[19] G.R. Grimmett. The Random-Cluster Model, volume 333 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Ver- lag, Berlin, 2006.
[20] H. Guo and M. Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1818–1827. SIAM, 2017.
[21] S. Janson, T. Łuczak, and A. Ruciński. Random Graphs. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2011.
[22] D.A. Levin and Y. Peres. Markov Chains and Mixing Times. MBK. American Mathematical Society, 2017.
[23] D.A. Levin, Y. Peres, and E.L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.
[24] Y. Long, A. Nachmias, W. Ning, and Y. Peres. A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics. Memoirs of the American Mathematical Society, 232(1092), 2011.
[25] Malwina Luczak and Tomasz Luczak. The phase transition in the cluster-scaled model of a random graph. Random Structures & Algorithms, 28(2):215–246, 2006.
[26] T. Luczak. Cycles in a random graph near the critical point. Random Structures & Algorithms, 2(4):421–439, 1991.
[27] T. Łuczak, B. Pittel, and J.C. Wierman. The structure of a random graph at the point of the phase transition. Transactions of the American Mathematical Society, 341(2):721–748, 1994.
[28] A.B. Mukhin. Local limit theorems for lattice random variables. Theory of Probability & Its Applications, 36(4):698–713, 1992.
[29] B. Pittel. On tree census and the giant component in sparse random graphs. Random Structures & Algorithms, 1(3):311–342, 1990.
[30] R.H. Swendsen and J.S. Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Physical Review Letters, 58:86–88, 1987.
[31] M. Ullrich. Swendsen-Wang is faster than single-bond dynamics. SIAM Journal on Discrete Mathematics, 28(1):37–48, 2014.
[32] Roman Vershynin. High-dimensional probability. 2019.

Appendix A Proof of the local limit theorem

In this appendix, we prove Theorem 5.1. First, we introduce some notation. For a random variable $X$ and $d\in\mathbb{R}$ , let $H(X,d)=\operatorname*{{\rm E}}[\langle X^{*}d\rangle^{2}]$ , where $\langle\cdot\rangle$ denotes distance to the closest integer and $X^{*}$ is a symmetrized version of $X$ ; i.e., $X^{*}=X-X^{\prime}$ where $X^{\prime}$ is an i.i.d. copy of $X$ . Let $H_{m}=\inf_{d\in[\frac{1}{4},\frac{1}{2}]}\,\,\sum_{i=1}^{m}H(X_{i},d)$ . The following local limit theorem is due to Mukhin [28] (all limits are taken as $m\rightarrow\infty$ ).

Theorem A.1 ([28], Theorem 1).

Suppose that the sequence $\frac{S_{m}-\mu_{m}}{\sigma_{m}}$ converges in distribution to a standard normal random variable and that $\sigma_{m}\rightarrow\infty$ . If $H_{m}\rightarrow\infty$ and there exists $\alpha>0$ such that $\forall u\in[H_{m}^{1/4},\sigma_{m}]$ we have $\sum_{i:c_{i}\leq u}c_{i}^{2}\geq\alpha u\sigma_{m},$ then the local limit theorem holds.

Next, we show how to derive Theorem 5.1 from Theorem A.1. The proof involves the following two lemmas.

Lemma A.2.

For the random variables satisfying the conditions from Theorem 5.1, $\sigma_{m}\rightarrow\infty$ and $\frac{S_{m}-\mu_{m}}{\sigma_{m}}$ converges in distribution to a standard normal random variable.

Proof.

Observe that

\sigma_{m}^{2}=r(1-r)\sum_{i=1}^{m}c_{i}^{2}\geq r(1-r)\sum_{i:c_{i}\in I_{1}}c_{i}^{2}=\Omega\left(\frac{m^{4/3}}{g(m)^{4}}\cdot g(m)^{3}\right)=\Omega\left(\frac{m^{4/3}}{g(m)}\right)\rightarrow\infty,

and also

	$\displaystyle\frac{1}{\sigma_{m}^{3}}\sum_{i=1}^{m}\operatorname{{\rm E}}[\|X_{i}-\operatorname{{\rm E}}[X_{i}]\|^{3}]$	$\displaystyle=\frac{1}{\sigma_{m}^{3}}\sum_{i=1}^{m}r(1-r)c_{i}^{3}\leq\frac{\sigma^{2}_{m}c_{m}}{\sigma^{3}_{m}}=O\left(\frac{c_{m}}{\sigma_{m}}\right)$
		$\displaystyle=O\left(\frac{m^{2/3}g(m)^{-1}}{m^{2/3}g(m)^{-1/2}}\right)=O\left(g(m)^{-1/2}\right)\rightarrow 0.$

Hence, the random variables $\{X_{i}\}$ satisfy Lyapunov’s central limit theorem conditions (see, e.g., [13]), and so $\frac{S_{m}-\mu_{m}}{\sigma_{m}}$ converges in distribution to a standard normal random variable. ∎

Lemma A.3.

Suppose $c_{1},\dots,c_{m}$ satisfy the conditions from Theorem 5.1. For any $u$ satisfying $\sigma_{m}\geq u\geq 1$ , $\sum_{j:c_{j}\leq u}c_{j}^{2}\geq u\sigma_{m}/r(1-r)$ .

Proof.

We have $\sigma_{m}^{2}=r(1-r)\sum_{i=1}^{m}c_{i}^{2}=O\left(\frac{m^{4/3}}{\sqrt{g(m)}}\right).$ We consider three cases. First, if $m^{1/4}\leq u\leq c_{m}=O\left(m^{2/3}g(m)^{-1}\right)$ , there exists a largest integer $k\in[0,\ell)$ such that $u=O\left(\frac{\vartheta m^{2/3}}{g(m)^{2^{k}}}\right)$ , where $\ell>0$ is the smallest integer such that $m^{2/3}g(m)^{-2^{\ell}}=o(m^{1/4})$ . Then,

\sum_{i:c_{i}\leq u}c_{i}^{2}\geq\sum_{i:c_{i}\in I_{k+1}}c_{i}^{2}\geq\frac{\vartheta^{2}m^{4/3}}{4g(m)^{2^{k+2}}}g(m)^{3\cdot 2^{k}}=\frac{\vartheta^{2}m^{4/3}}{4g(m)^{2^{k}}}\gg u\sigma_{m};

by $\gg$ we mean that $u\sigma_{m}$ is of lower order with respect to $\frac{\vartheta^{2}m^{4/3}}{4g(m)^{2^{k}}}$ . Now, when $\sigma_{m}\geq u\geq c_{m}$ , we have

\sum_{i:c_{i}\leq u}c_{i}^{2}=\sum_{i=1}^{m}c_{i}^{2}=\frac{\sigma_{m}^{2}}{r(1-r)}\geq\frac{u\sigma_{m}}{r(1-r)}.

Finally, if $1\leq u\leq m^{1/4}$ , $u\sigma_{m}$ is sublinear and so

\sum_{i:c_{i}\leq u}c_{i}^{2}\geq\sum_{i=1}^{\rho m}c_{i}^{2}=\rho m\gg m^{1/4}\sigma_{m}\geq u\sigma_{m},

as claimed. ∎

Proof of Theorem 5.1.

We check that the $X_{i}$ ’s satisfy the conditions from Theorem A.1. Lemma A.2 implies $\sigma_{m}\rightarrow\infty$ and $\frac{S_{m}-\mu_{m}}{\sigma_{m}}\rightarrow N(0,1)$ ; by Lemma A.3 we also have that for any $u$ satisfying $\sigma_{m}\geq u\geq 1$ , $\sum_{j:c_{j}\leq u}c_{j}^{2}\geq u\sigma_{m}/r(1-r)$ . It remains to show that $H_{m}\rightarrow\infty$ .

Now, for $i\leq\rho m$ , observe that the value of $X^{*}_{i}$ equals to $1$ with probability $r(1-r)$ , $-1$ with probability $r(1-r)$ , and $0$ otherwise. Then for $1/4\leq d\leq 1/2$ , $\langle X_{i}^{*}d\rangle^{2}$ evaluates to $d^{2}$ with probability $2r(1-r)$ , and $0$ otherwise. Therefore, for $i\leq\rho m$ and $1/4\leq d\leq 1/2$ we have that $\operatorname*{{\rm E}}[\langle X_{i}^{*}d\rangle^{2}]=2r(1-r)d^{2}.$ Thus,

H_{m}=\inf_{\frac{1}{4}\leq d\leq\frac{1}{2}}\sum_{i=1}^{m}H(X_{i},d)\geq\inf_{\frac{1}{4}\leq d\leq\frac{1}{2}}\sum_{i=1}^{\lfloor\rho m\rfloor}H(X_{i},d)=\inf_{\frac{1}{4}\leq d\leq\frac{1}{2}}\sum_{i=1}^{\lfloor\rho m\rfloor}2r(1-r)d^{2}=\Omega(m)\rightarrow\infty.

Since we have shown that the $X_{i}$ ’s satisfy all the conditions from Theorem A.1, the result follows. ∎

For completeness, we also derive Theorem 5.1 from first principles (i.e. without using Mukhin’s result [28]) in Appendix D.

Appendix B Proofs of random walk couplings

Another important tool in our proofs are couplings based on the evolutions of certain random walks. In this section we consider a (lazy) symmetric random walk $(S_{k})$ on $\mathbb{Z}$ with bounded step size, and the first result we present is an estimate on $M_{k}=\max\{S_{1},\dots,S_{k}\}$ which is based on the well-known reflection principle (see, e.g., Chapter 2.7 in [22]).

Lemma B.1.

Let $A>0$ and let $A\leq c_{1},c_{2},\dots,c_{n}\leq 4A$ be positive integers. Let $r\in(0,1/2]$ and consider the sequence of random variables $X_{1},\dots,X_{n}$ where for each $i=1,\dots,n$ : $X_{i}=c_{i}$ with probability $r$ ; $X_{i}=-c_{i}$ with probability $r$ ; and $X_{i}=0$ otherwise. Let $S_{k}=\sum_{i=1}^{k}X_{i}$ and $M_{k}=\max\{S_{1},\dots,S_{k}\}$ . Then, for any $y\geq 0$

\Pr[M_{n}\geq y]\geq 2\Pr[S_{n}\geq y+8A+1].

Proof.

First, note that

	$\displaystyle\Pr[M_{n}\geq y]$	$\displaystyle=\sum_{k=y}^{4An}\Pr[M_{n}\geq y,S_{n}=k]+\sum_{k=-4An}^{y-1}\Pr[M_{n}\geq y,S_{n}=k]$
		$\displaystyle=\Pr[S_{n}\geq y]+\sum_{k=-4An}^{y-1}\Pr[M_{n}\geq y,S_{n}=k].$		(26)

If $M_{n}\geq y$ , let $W_{n}$ be the value of the random walk $\{S_{i}\}$ the first time its value was at least $y$ . Then,

	$\displaystyle\Pr[M_{n}\geq y,S_{n}=k]$	$\displaystyle=\sum_{b=y}^{y+4A-1}\Pr[M_{n}\geq y,S_{n}=k,W_{n}=b]$
		$\displaystyle=\sum_{b=y}^{y+4A-1}\Pr[M_{n}\geq y,S_{n}=2b-k,W_{n}=b]$
		$\displaystyle=\sum_{b=y}^{y+4A-1}\Pr[S_{n}=2b-k,W_{n}=b],$

where in the second equality we used the fact that the random walk is symmetric and the last one follows from the fact that $2b-k\geq y$ . Plugging this into (26), we get

	$\displaystyle\Pr[M_{n}\geq y]$	$\displaystyle=\Pr[S_{n}\geq y]+\sum_{b=y}^{y+4A-1}\sum_{k=-4An}^{y-1}\Pr[S_{n}=2b-k,W_{n}=b]$
		$\displaystyle=\Pr[S_{n}\geq y]+\sum_{b=y}^{y+4A-1}\sum_{k=2b-y+1}^{4An}\Pr[S_{n}=k,W_{n}=b]$
		$\displaystyle=\Pr[S_{n}\geq y]+\sum_{b=y}^{y+4A-1}\Pr[S_{n}\geq 2b-y+1,W_{n}=b]$
		$\displaystyle\geq\Pr[S_{n}\geq y]+\sum_{b=y}^{y+4A-1}\Pr[S_{n}\geq y+8A+1,W_{n}=b],$

since $b<y+4A$ . Finally, observe that

\sum_{b=y}^{y+4A-1}\Pr[S_{n}\geq y+8A+1,W_{n}=b]=\Pr[S_{n}\geq y+8A+1]

and so

\Pr[M_{n}\geq y]\geq\Pr[S_{n}\geq y]+\Pr[S_{n}\geq y+8A+1]\geq 2\Pr[S_{n}\geq y+8A+1],

as desired. ∎

We can now prove Theorem 5.7.

Proof of Theorem 5.7.

Set $\delta=\frac{10}{\sqrt{r}}$ . Let $D_{k}=\sum_{i=1}^{k}(X_{i}-Y_{i})$ for each $k\in\{1,\dots,m\}$ . We construct a coupling for $(X,Y)$ by coupling each $(X_{k},Y_{k})$ as follows:

1.

If $D_{k}<d$ , sample $X_{k+1}$ and $Y_{k+1}$ independently.
2.

If $D_{k}\geq d$ , set $X_{k+1}=Y_{k+1}$ .

Observe that if $D_{k}\geq d$ for any $k\leq m$ , then $d+2A\geq X-Y\geq d$ . Therefore,

\Pr[d+2A\geq X-Y\geq d]\geq\Pr[M_{m}\geq d]

where $M_{m}=\max\{D_{0},...,D_{m}\}$ . Note that $\{D_{k}\}$ behaves like a (lazy) symmetric random walk until the first time $\tau$ it is at least $d$ ; after that $\{D_{k}\}$ stays put.

Let $\{D^{\prime}_{k}\}$ denote such random walk which does not stop after $\tau$ , and $M^{\prime}_{m}:=\max\{D^{\prime}_{0},...,D^{\prime}_{m}\}$ . Notice

\Pr[M_{m}\geq d]=\Pr[M^{\prime}_{m}\geq d].

Since the step size of $\{D^{\prime}_{k}\}$ is at least $A$ and at most $4A$ , by Lemma B.1 for any $d\geq 0$

\Pr[M^{\prime}_{m}\geq d]\geq 2\Pr[D^{\prime}_{m}\geq d+8A+1].

Let $\sigma^{2}=\sum_{i=1}^{m}\operatorname*{{\rm E}}[(X_{i}-Y_{i})^{2}]=4r\sum_{i=1}^{m}c_{i}^{2}$ and $\rho=\sum_{i=1}^{m}\operatorname*{{\rm E}}[|X_{i}-Y_{i}|^{3}]=4r(1+2r)\sum_{i=1}^{m}c_{i}^{3}$ . By the Berry-Esséen theorem for independent (but not necessarily identical) random variables (see, e.g. [3]), we get that for any $y\in\mathbb{R}$

\left|\Pr[D^{\prime}_{m}>y\sigma]-\Pr[N>y]\right|\leq\frac{c\rho}{\sigma^{3}}\leq\frac{2cA}{\sigma}.

where $N$ is a standard normal random variable, and $c\in[0.4,0.6]$ is an absolute constant. Then,

\Pr[D^{\prime}_{m}>y\sigma]\geq\Pr[N>y]-\frac{2cA}{\sigma}.

(27)

Notice $\sigma\geq 2A\sqrt{rm}$ . If $d+8A\geq\sigma$ , the theorem holds vacuously since

1-\frac{\delta(d+A)}{A\sqrt{m}}=1-\frac{10(d+A)}{A\sqrt{rm}}<1-\frac{d+8A}{A\sqrt{rm}}\leq 1-\frac{\sigma}{A\sqrt{rm}}\leq 1-2<0.

If $d+8A<\sigma$ , since it can be checked via a Taylor’s expansion that $2\Pr[N>y]\geq 1-\sqrt{\frac{2}{\pi}}y$ for $y<1$ , we get from (27)

	$\displaystyle\Pr[M_{m}\geq d]\geq 2\Pr[D^{\prime}_{m}>d+8A]$	$\displaystyle\geq 2\Pr\left[N>\frac{d+8A}{\sigma}\right]-\frac{4cA}{\sigma}$
		$\displaystyle\geq 1-\frac{\sqrt{2/\pi}(d+8A)}{\sigma}-\frac{4cA}{\sigma}$
		$\displaystyle\geq 1-\frac{9(d+A)}{\sigma}$
		$\displaystyle\geq 1-\frac{\delta(d+A)}{A\sqrt{m}},$

as claimed. ∎

Appendix C Random graphs estimates

In this section, we provide proofs of lemmas which do not appear in the literature.

Recall $G\sim G(n,\frac{1+\lambda n^{-1/3}}{n})$ , where $\lambda=\lambda(n)$ may depend on $n$ . Both of Lemmas 3.10 and 3.11 are proved using the following precise estimates on the moments of the number of trees of a given size in $G$ . We note that similar estimates can be found in the literature (see, e.g., [29, 1]); a proof is included for completeness.

Claim C.1.

Let $t_{k}$ be the number of trees of size $k$ in $G$ . Suppose there exists a positive increasing function $g$ such that $g(n)\rightarrow\infty$ , $|\lambda|\leq g(n)$ and $i,j,k\leq\frac{n^{2/3}}{g(n)^{2}}$ . If $i,j,k\rightarrow\infty$ as $n\rightarrow\infty$ , then:

(i)

$\operatorname*{{\rm E}}[t_{k}]=\Theta\left(\frac{n}{k^{5/2}}\right)$ ;
(ii)

$\operatorname*{{\rm Var}}(t_{k})\leq\operatorname*{{\rm E}}[t_{k}]+\frac{(1+o(1))\lambda n^{2/3}}{2\pi k^{3}}$ ;
(iii)

For $i\neq j$ , $\operatorname*{{\rm Cov}}(t_{i},t_{j})\leq\frac{(1+o(1))\lambda n^{2/3}}{2\pi i^{3/2}j^{3/2}}$ .

To prove Lemma 3.10, we also use the following result.

Lemma C.2.

Suppose $\varepsilon^{3}n\rightarrow\infty$ and $\varepsilon=o(1)$ . Then w.h.p. the largest component of $G\sim G\left(n,\frac{1+\varepsilon}{n}\right)$ is the only component of $G$ which contains more than one cycle. Also, w.h.p. the number of vertices contained in the unicyclic components of $G$ is less than $g(n)\varepsilon^{-2}$ for any function $g(n)\rightarrow\infty$ .

Proof.

An equivalent result was established in [26] for the $G(n,M)$ model, in which exactly $M$ edges are chosen independently at random from the set of all $\binom{n}{2}$ possible edges (see Theorem 7 in [26]). The result follows from the asymptotic equivalence between the $G(n,p)$ and $G(n,M)$ models when $M=\binom{n}{2}p$ (see, e.g., Proposition 1.12 in [21]). ∎

Proof of Lemma 3.10.

Let us fix $\alpha>0$ and consider first the case when $|\lambda|$ is large. If $\lambda<0$ and $|\lambda|=\Omega(h(n)^{1/2})$ , then Lemma 3.7 implies that

\operatorname*{{\rm E}}\left[\sum\nolimits_{j:L_{j}(G)\leq B_{h}}L_{j}(G)^{2}\right]\leq\operatorname*{{\rm E}}[\mathcal{R}_{1}(G)]=O\left(\frac{n}{\lambda n^{-1/3}}\right)=O\left(\frac{n^{4/3}}{h(n)^{1/2}}\right).

Similarly, if $\lambda>0$ and $\lambda=\Omega(h(n)^{1/2})$ , then Lemma 3.8 implies that $\operatorname*{{\rm E}}[\mathcal{R}_{2}(G)]=O(n^{4/3}h(n)^{-1/2})$ . We may assume $L_{1}(G)\leq B_{h}$ since otherwise the size of the largest component does not contribute to the sum. Then,

\operatorname*{{\rm E}}\left[\sum\nolimits_{j:L_{j}(G)\leq B_{h}}L_{j}(G)^{2}\right]\leq\operatorname*{{\rm E}}[\mathcal{R}_{2}(G)]+B_{h}^{2}=O\left(\frac{n^{4/3}}{h(n)^{1/2}}\right).

Hence, if $|\lambda|=\Omega(h(n)^{-1/2})$ , the result follows from Markov’s inequality.

Suppose next $|\lambda|\leq\sqrt{h(n)}$ . Let $t_{k}$ be the number of trees of size $k$ in $G$ and let $\mathcal{T}_{B_{h}}$ be the set of trees of size at most $B_{h}$ in $G$ . By Claim C.1.i,

	$\displaystyle\operatorname*{{\rm E}}\left[\sum\nolimits_{\tau\in\mathcal{T}_{B_{h}}}\|\tau\|^{2}\right]$	$\displaystyle=\sum_{k=1}^{B_{h}}k^{2}\operatorname{{\rm E}}[t_{k}]=O(nh(n)^{2})+\sum_{k=\lfloor h(n)\rfloor}^{B_{h}}k^{2}\operatorname{{\rm E}}[t_{k}]$
		$\displaystyle=O(nh(n)^{2})+O(n)\sum_{k=\lfloor h(n)\rfloor}^{B_{h}}\frac{1}{k^{1/2}}=O\left(\frac{n^{4/3}}{h(n)^{1/2}}\right).$		(28)

By Markov’s inequality, we get that $\sum\nolimits_{\tau\in\mathcal{T}_{B_{h}}}|\tau|^{2}\leq An^{4/3}h(n)^{-1/2}$ with probability at least $\gamma$ , for any desired $\gamma>0$ for a suitable constant $A=A(\gamma)>0$ .

All that is left to prove is that the contribution from complex (non-tree) components is small. When $|\lambda|=O(1)$ , this follows immediately from the fact that the expected number of complex components is $O(1)$ (see, e.g., Lemma 2.1 in [27]). Then, if $\mathcal{C}_{B_{h}}$ is the set of complex components in $G$ of size at most $B_{h}$ , we have

\operatorname*{{\rm E}}\left[\sum\nolimits_{C\in\mathcal{C}_{B_{h}}}|C|^{2}\right]=O\left(\frac{n^{4/3}}{h(n)^{2}}\right)\operatorname*{{\rm E}}\left[\left\lvert\mathcal{C}_{B_{h}}\right\rvert\right]=O\left(\frac{n^{4/3}}{h(n)^{2}}\right),

and the result follows again from Markov’s inequality and a union bound.

Finally, when $\sqrt{h(n)}\geq|\lambda|\rightarrow\infty$ , Lemma C.2 implies that w.h.p. there is no multicyclic component except the largest component and that the number of vertices in unicyclic components is bounded by $n^{2/3}g(n)/\lambda^{2}$ , for any function $g(n)\rightarrow\infty$ . Hence, w.h.p.,

\sum\nolimits_{C\in\mathcal{C}_{B_{h}}}|C|\leq\frac{n^{2/3}g(n)}{\lambda^{2}}+B_{h}.

Setting $g(n)=\lambda^{2}$ , it follows that w.h.p.

\sum\nolimits_{C\in\mathcal{C}_{B_{h}}}|C|^{2}\leq B_{h}\left(\frac{n^{2/3}g(n)}{\lambda^{2}}+B_{h}\right)\leq\frac{n^{4/3}}{h(n)}.

This, combined with (C), Markov’s inequality and a union bound yields the result. ∎

Proof of Lemma 3.11.

Let $T_{B}$ be number of trees in $G$ with size in the interval $[B,2B]$ ; then $|S_{B}|\geq T_{B}$ . By Chebyshev’s inequality for $a>0$ :

\Pr[T_{B}\leq\operatorname*{{\rm E}}[T_{B}]-a\sigma]\leq\frac{1}{a^{2}},

where $\sigma^{2}=\operatorname*{{\rm Var}}(T_{B})$ . By Claim C.1.i,

\operatorname*{{\rm E}}[T_{B}]=\sum_{k=B}^{2B}\operatorname*{{\rm E}}[T_{k}]\geq\frac{c_{1}n}{B^{3/2}}

for a suitable constant $c_{1}>0$ . Now,

\operatorname*{{\rm Var}}(T_{B})=\sum_{k=B}^{2B}\operatorname*{{\rm Var}}(t_{k})+\sum_{j\neq i:j,i\in[B,2B]}\operatorname*{{\rm Cov}}(t_{i},t_{j}).

By Claim C.1.i and Claim C.1.ii,

\sum_{k=B}^{2B}\operatorname*{{\rm Var}}(t_{k})\leq\sum_{k=B}^{2B}\operatorname*{{\rm E}}[t_{k}]+\sum_{k=B}^{2B}\frac{(1+o(1))\lambda n^{2/3}}{2\pi k^{3}}=O\left(\frac{n}{B^{3/2}}\right)+O\left(\frac{|\lambda|n^{2/3}}{B^{2}}\right)=O\left(\frac{n}{B^{3/2}}\right),

where in the last equality we used the assumption that $\lambda=o(n^{1/3})$ . Similarly, by Claim C.1.iii

\sum_{j\neq i:j,i\in[B,2B]}\operatorname*{{\rm Cov}}(t_{i},t_{j})\leq\sum_{j\neq i:j,i\in[B,2B]}\frac{(1+o(1))\lambda n^{2/3}}{2\pi i^{3/2}j^{3/2}}\leq\frac{(1+o(1))|\lambda|n^{2/3}}{2\pi B}=O\left(\frac{n}{B^{3/2}}\right),

where the last inequality follows from the assumption that $B\leq\frac{n^{2/3}}{g(n)^{2}}$ . Hence, for a suitable constant $c_{2}>0$

\operatorname*{{\rm Var}}(T_{B})\leq\frac{c_{2}n}{B^{3/2}}

and taking $a=\frac{c_{1}n}{2B^{3/2}\sigma}$ we get

\Pr\left[|S_{B}|\leq\frac{c_{1}n}{2B^{3/2}}\right]\leq\Pr\left[T_{B}\leq\frac{c_{1}n}{2B^{3/2}}\right]\leq\left(\frac{2B^{3/2}\sigma}{c_{1}n}\right)^{2}\leq\frac{4c_{2}B^{3/2}}{c_{1}^{2}n},

as desired. ∎

Proof Corollary 3.12.

Lemma 3.11 implies that for a suitable constant $b>0$

\Pr\left[N_{k}(X_{t+1},g)<bg(n)^{3\cdot 2^{k-1}}\right]=O(g(n)^{-3\cdot 2^{k-1}}),

for any $k\geq 1$ such that $g(n)^{2^{k}}=o(m^{2/3})$ . Observe that

\sum_{k\geq 1}\frac{1}{g(n)^{3\cdot 2^{k-1}}}\leq\sum_{i\geq 1}\frac{1}{g(n)^{3i}}=O(g(n)^{-3}).

Hence, a union bound over $k$ , i.e., over the intervals $\mathcal{I}_{k}(g)$ , implies that, with probability at least $1-O(g(n)^{-3})$ , $N_{k}(X_{t+1},g)\geq bg(n)^{3\cdot 2^{k-1}}$ for all $k\geq 1$ such that $n^{2/3}g(n)^{-2^{k}}\rightarrow\infty$ , as claimed. ∎

Proof of Claim C.1.

Let $c=1+\lambda n^{-1/3}$ . The following combinatorial identity follows immediately from the fact that there are exactly $k^{k-2}$ trees of size $k$ .

\operatorname*{{\rm E}}[t_{k}]=\binom{n}{k}k^{k-2}\left(\frac{c}{n}\right)^{k-1}\left(1-\frac{c}{n}\right)^{k(n-k)+\binom{k}{2}-k+1}.

Using the Taylor expansion for $\ln(1-x)$ and the fact that $k=o(n^{2/3})$ , we get

\displaystyle\frac{n!}{(n-k)!}

\displaystyle=n^{k}\,\prod_{i=1}^{k-1}\left(1-\frac{i}{n}\right)=n^{k}\exp\left(-\frac{k^{2}}{2n}-\frac{k^{3}}{6n^{2}}+o(1)\right).

(29)

Similarly,

	$\displaystyle\left(\frac{c}{n}\right)^{k-1}$	$\displaystyle=\frac{1}{n^{k-1}}\exp\left(\frac{\lambda k}{n^{1/3}}-\frac{\lambda^{2}k}{2n^{2/3}}+o(1)\right),$
	$\displaystyle\left(1-\frac{c}{n}\right)^{k(n-k)+\binom{k}{2}-k+1}$	$\displaystyle=\exp\left(-k-\frac{\lambda k}{n^{1/3}}+\frac{k^{2}}{2n}+\frac{\lambda k^{2}}{2n^{4/3}}+o(1)\right).$

Since $k\rightarrow\infty$ , Stirling’s approximation gives

\frac{k^{k-2}}{k!}=\frac{(1+o(1))e^{k}}{\sqrt{2\pi}k^{5/2}}.

(30)

Putting all these bounds together, we get

\displaystyle\operatorname*{{\rm E}}[t_{k}]=\frac{(1+o(1))n}{\sqrt{2\pi}k^{5/2}}\exp\left(-\frac{\lambda^{2}k}{2n^{2/3}}+\frac{\lambda k^{2}}{2n^{4/3}}-\frac{k^{3}}{6n^{2}}\right)=\Theta\left(\frac{n}{k^{5/2}}\right),

(31)

where in the last inequality we used the assumptions that $|\lambda|\leq g(n)$ and $k\leq\frac{n^{2/3}}{g(n)^{2}}$ . This establishes part (i).

For part (ii) we proceed in similar fashion, starting instead from the following combinatorial identity:

\operatorname*{{\rm E}}[t_{k}(t_{k}-1)]=\frac{n!}{k!k!(n-2k)!}(k^{k-2})^{2}\left(\frac{c}{n}\right)^{2k-2}\left(1-\frac{c}{n}\right)^{m},

where $m=2\binom{k}{2}-2(k-1)+k^{2}+2k(n-2k)$ (see, e.g., [29]). Using the Taylor expansion for $\ln(1-x)$ , we get

	$\displaystyle\frac{n!}{(n-2k)!}$	$\displaystyle=n^{2k}\exp\left(-\frac{2k^{2}}{n}-\frac{4k^{3}}{3n^{2}}+o(1)\right),$
	$\displaystyle\left(\frac{c}{n}\right)^{2k-2}$	$\displaystyle=\frac{1}{n^{2k-2}}\exp\left(\frac{2\lambda k}{n^{1/3}}-\frac{\lambda^{2}k}{n^{2/3}}+o(1)\right),$
	$\displaystyle\left(1-\frac{c}{n}\right)^{m}$	$\displaystyle=\exp\left(-2k+\frac{2k^{2}}{n}-\frac{2\lambda k}{n^{1/3}}+\frac{2\lambda k^{2}}{n^{4/3}}+o(1)\right).$

These three bounds together with (30) imply

\operatorname*{{\rm E}}[t_{k}(t_{k}-1)]=\frac{(1+o(1))n^{2}}{2\pi k^{5}}\exp\left(-\frac{4k^{3}}{3n^{2}}-\frac{\lambda^{2}k}{n^{2/3}}+\frac{2\lambda k^{2}}{n^{4/3}}\right).

From (31), we get

\operatorname*{{\rm E}}[t_{k}]^{2}=\frac{(1+o(1))n^{2}}{2\pi k^{5}}\exp\left(-\frac{\lambda^{2}k}{n^{2/3}}+\frac{\lambda k^{2}}{n^{4/3}}-\frac{k^{3}}{3n^{2}}\right).

Hence,

	$\displaystyle\operatorname*{{\rm Var}}(t_{k})$	$\displaystyle=\operatorname*{{\rm E}}[t_{k}]+\frac{(1+o(1))n^{2}}{2\pi k^{5}}\exp\left(-\frac{\lambda^{2}k}{n^{2/3}}+\frac{\lambda k^{2}}{n^{4/3}}-\frac{k^{3}}{3n^{2}}\right)\left[\exp\left(\frac{\lambda k^{2}}{n^{4/3}}-\frac{k^{3}}{n^{2}}\right)-1\right]$
		$\displaystyle=\operatorname*{{\rm E}}[t_{k}]+\frac{(1+o(1))n^{2}}{2\pi k^{5}}\left[\exp\left(\frac{\lambda k^{2}}{n^{4/3}}-\frac{k^{3}}{n^{2}}\right)-1\right]$
		$\displaystyle\leq\operatorname*{{\rm E}}[t_{k}]+\frac{(1+o(1))n^{2}}{2\pi k^{5}}\left[\exp\left(\frac{\lambda k^{2}}{n^{4/3}}\right)-1\right]$
		$\displaystyle\leq\operatorname*{{\rm E}}[t_{k}]+\frac{(1+o(1))\lambda n^{2/3}}{2\pi k^{3}}$

where in the second equality we used the assumptions that $|\lambda|\leq g(n)$ and $k\leq\frac{n^{2/3}}{g(n)^{2}}$ and for the last inequality we used the Taylor expansion for $e^{x}$ . This completes the proof of part (ii).

For part (iii), let $\ell=i+j$ . When $i\neq j$ we have the following combinatorial identity (see, e.g., [29]):

\operatorname*{{\rm E}}[t_{i}t_{j}]=\frac{n!}{i!j!(n-\ell)!}i^{i-2}j^{j-2}\left(\frac{c}{n}\right)^{\ell-2}\left(1-\frac{c}{n}\right)^{m^{\prime}},

where $m^{\prime}=\binom{i}{2}-(i-1)+\binom{j}{2}-(j-1)+ij+\ell(n-\ell)$ . Using Taylor expansions and Stirling’s approximation as in the previous two parts, we get

\operatorname*{{\rm E}}[t_{i}t_{j}]=\frac{(1+o(1))n^{2}}{2\pi i^{5/2}j^{5/2}}\exp\left(-\frac{\ell^{3}}{6n^{2}}-\frac{\lambda^{2}\ell}{2n^{2/3}}+\frac{\lambda\ell^{2}}{2n^{4/3}}\right).

Moreover, from (31) we have

\operatorname*{{\rm E}}[t_{i}]\operatorname*{{\rm E}}[t_{j}]=\frac{(1+o(1))n^{2}}{2\pi i^{5/2}j^{5/2}}\exp\left(-\frac{\lambda^{2}\ell}{2n^{2/3}}+\frac{\lambda(i^{2}+j^{2})}{2n^{4/3}}-\frac{i^{3}+j^{3}}{6n^{2}}+o(1)\right),

and so

	$\displaystyle\operatorname*{{\rm Cov}}(t_{i},t_{j})$	$\displaystyle=\operatorname{{\rm E}}[t_{i}t_{j}]-\operatorname{{\rm E}}[t_{i}]\operatorname*{{\rm E}}[t_{j}]$
		$\displaystyle=\frac{(1+o(1))n^{2}}{2\pi i^{5/2}j^{5/2}}\exp\left(-\frac{\ell^{3}}{6n^{2}}-\frac{\lambda^{2}\ell}{2n^{2/3}}+\frac{\lambda\ell^{2}}{2n^{4/3}}\right)\left[1-\exp\left(-\frac{\lambda ij}{n^{4/3}}+\frac{ij\ell}{2n^{2}}\right)\right]$
		$\displaystyle=\frac{(1+o(1))n^{2}}{2\pi i^{5/2}j^{5/2}}\left[1-\exp\left(-\frac{\lambda ij}{n^{4/3}}+\frac{ij(i+j)}{2n^{2}}\right)\right]$
		$\displaystyle\leq\frac{(1+o(1))\lambda n^{2/3}}{2\pi i^{3/2}j^{3/2}}$

where in the third equality we used the assumptions that $|\lambda|\leq g(n)$ and $i,j\leq\frac{n^{2/3}}{g(n)^{2}}$ and the last inequality follows from the Taylor expansion for $e^{x}$ . ∎

Appendix D The second proof of the local limit theorem

In this appendix, we provide an alternative proof of Theorem 5.1 that does not use Theorem A.1.

Proof of Theorem 5.1.

Let $\Phi(\cdot)$ denote the probability density function of a standard normal distribution. We will show for any fixed $a\in\mathbb{R}$ ,

\left\lvert\Pr\left[\frac{S_{m}-\mu_{m}}{\sigma_{m}}=a\right]-\frac{\Phi(a)}{\sigma_{m}}\right\rvert=o\left(\frac{1}{\sigma_{m}}\right),

(32)

which is equivalent to (9).

Let $\phi(t)$ denote the characteristic function for the random variable $(S_{m}-\mu_{m})/\sigma_{m}$ . By applying the inversion formula (see Theorem 3.3.14 and Exercise 3.3.2 in [13]),

\Phi(a)=\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-ita}e^{-t^{2}/2}dt,

and

\Pr\left[\frac{S_{m}-\mu_{m}}{\sigma_{m}}=a\right]=\frac{1}{2\pi\sigma_{m}}\int_{-\pi\sigma_{m}}^{\pi\sigma_{m}}e^{-ita}\phi(t)dt.

Hence, the left hand side of (32) can be bounded from above by

\frac{1}{2\pi\sigma_{m}}\left[\int_{-\pi\sigma_{m}}^{\pi\sigma_{m}}\left\lvert e^{-ita}\left(\phi(t)-e^{-\frac{t^{2}}{2}}\right)\right\rvert dt+2\int_{\pi\sigma_{m}}^{\infty}e^{-\frac{t^{2}}{2}}dt\right].

Since $|e^{-ita}|\leq 1$ , it suffices to show that for all $\varepsilon>0$ there exists $M>0$ such that if $m>M$ then

\int_{-\pi\sigma_{m}}^{\pi\sigma_{m}}\left\lvert\phi(t)-e^{-\frac{t^{2}}{2}}\right\rvert dt+2\int_{\pi\sigma_{m}}^{\infty}e^{-\frac{t^{2}}{2}}dt\leq\varepsilon.

(33)

We can bound from above the left hand side of (33) by:

\int_{-A}^{A}\left\lvert\phi(t)-e^{-\frac{t^{2}}{2}}\right\rvert dt+2\int_{A}^{\sigma_{m}/2}\left\lvert\phi(t)\right\rvert dt+2\int_{\sigma_{m}/2}^{\pi\sigma_{m}}\left\lvert\phi(t)\right\rvert dt+2\int_{A}^{\infty}e^{-\frac{t^{2}}{2}}dt.

(34)

The division depends on some constant $A$ that we will choose soon. We proceed to bound integral terms in (34) independently.

Lemma A.2 implies that $\frac{S_{m}-\mu_{m}}{\sigma_{m}}$ converges in distribution to a standard normal. Combined with the continuity theorem (see Theorem 3.3.17 in [13]), we get that $\phi(t)\rightarrow e^{-\frac{t^{2}}{2}}$ as $m\rightarrow\infty$ . The dominated convergence theorem (see Theorem 1.5.8 in [13]) hence implies that for any $A<\infty$ the first integral of (34) converges to 0. We select $M$ large enough so that the integral is less than $\varepsilon/4$ .

The last integral of (34) is the standard normal tail that goes to $0$ exponentially fast as $A$ increases (see e.g. Proposition 2.1.2 in [32]). Therefore, we are able to select $A$ large enough so that each tail has probability mass less than $\varepsilon/8$ .

To bound the remaining two terms we use the properties of the characteristic function $\phi(t)$ . By definition and the independence between $X_{i}$ ’s,

\phi(t)=\operatorname*{{\rm E}}\left[\exp\left(it\cdot\frac{S_{m}-\mu_{m}}{\sigma_{m}}\right)\right]=\exp\left(-\frac{it\mu_{m}}{\sigma_{m}}\right)\prod_{j=1}^{m}\phi_{j}(t),

where $\phi_{j}(t)$ denotes the characteristic function of $X_{j}/\sigma_{m}$ . Since $\exp(-\frac{it\mu_{m}}{\sigma_{m}})$ always has modulo 1, $\lvert\phi(t)\rvert\leq\prod_{j=1}^{m}\lvert\phi_{j}(t)\rvert$ .

We proceed to bound the third integral of (34). Note that $\lvert\phi_{j}(t)\rvert\leq 1$ for all $j$ and $t$ . Therefore,

\lvert\phi(t)\rvert\leq\prod_{j=1}^{m}|\phi_{j}(t)|\leq\prod_{j\leq\rho m}|\phi_{j}(t)|.

Notice that the $X_{j}$ ’s for $j\leq\rho m$ are Bernoulli random variables. By periodicity (see Theorem 3.5.2 in [13]), $|\phi_{j}(t)|$ equals to 1 only when $t$ equals to the multiples of $2\pi\sigma_{m}$ . For $t\in[\sigma_{m}/2,\sigma_{m}\pi]$ , $|\phi_{j}(t)|$ is bounded away from $1$ , and there exists a constant $\eta<1$ such that $\lvert\phi_{j}(t)\rvert\leq\eta$ . Hence, $\lvert\phi(t)\rvert\leq\eta^{\rho m}$ . By choosing $M$ to be sufficiently large, we may bound the integral for $m>M$ :

\int_{\sigma_{m}/2}^{\pi\sigma_{m}}\left\lvert\phi(t)\right\rvert dt\leq\int_{\sigma_{m}/2}^{\pi\sigma_{m}}\eta^{\rho m}dt\leq\pi\sigma_{m}\eta^{\rho m}\leq m\eta^{\rho m}\leq\frac{\varepsilon}{8}.

Finally, we bound the second integral of (34). By the definition of $X_{j}$ , we have

\phi_{j}(t)=re^{it\cdot\frac{c_{j}}{\sigma_{m}}}+(1-r)=r\cdot\left(\cos\frac{c_{j}t}{\sigma_{m}}+i\cdot\sin\frac{c_{j}t}{\sigma_{m}}\right)+1-r,

where the last identity uses Euler’ formula. Take the modulo of both sides,

	$\displaystyle\lvert\phi_{j}(t)\rvert$	$\displaystyle=\sqrt{r^{2}\sin^{2}\frac{c_{j}t}{\sigma_{m}}+\left(r\frac{c_{j}t}{\sigma_{m}}+1-r\right)^{2}}$
		$\displaystyle=\sqrt{r^{2}\sin^{2}\frac{c_{j}t}{\sigma_{m}}+r^{2}\cos^{2}\frac{c_{j}t}{\sigma_{m}}+(1-r)^{2}+2r(1-r)\cos\frac{c_{j}t}{\sigma_{m}}}$
		$\displaystyle=\sqrt{r^{2}+(1-r)^{2}+2r(1-r)\cos\frac{c_{j}t}{\sigma_{m}}}$
		$\displaystyle=\sqrt{1-2r(1-r)\left(1-\cos\frac{c_{j}t}{\sigma_{m}}\right)}$
		$\displaystyle=1-r(1-r)\left(1-\cos\frac{c_{j}t}{\sigma_{m}}\right)-\frac{1}{2}r^{2}(1-r)^{2}\left(1-\cos\frac{c_{j}t}{\sigma_{m}}\right)^{2}-\dots,$

where the last equality corresponds to the Taylor expansion for $\sqrt{1+y}$ when $\lvert y\rvert\leq 1$ . We can also Taylor expand $\cos\frac{c_{j}t}{\sigma_{m}}$ as

1-\frac{c_{j}^{2}t^{2}}{2\sigma_{m}^{2}}+\frac{c_{j}^{4}t^{4}}{4!\sigma_{m}^{4}}-\frac{c_{j}^{6}t^{6}}{6!\sigma_{m}^{6}}+\dots

Observe that if $\frac{c_{j}t}{\sigma_{m}}<1$ , then we can bound $\cos\frac{c_{j}t}{\sigma_{m}}$ from above by $1-\frac{c_{j}^{2}t^{2}}{4\sigma_{m}^{2}}$ . Furthermore, if we keep only the first order term from the expansion for $\lvert\phi_{j}(t)\rvert$ , we have

\lvert\phi_{j}(t)\rvert\leq 1-r(1-r)\frac{c_{j}^{2}t^{2}}{4\sigma_{m}^{2}}\leq\exp\left(-r(1-r)\frac{c_{j}^{2}t^{2}}{4\sigma_{m}^{2}}\right).

(35)

Note that (35) only holds if $c_{j}t<\sigma_{m}$ . However, if we fix $\sigma_{m}$ then for every $t\in[A,\sigma_{m}/2]$ , there always exists a real number $u(t)\geq 1$ such that $u(t)t<\sigma_{m}\leq 2u(t)t$ , which implies for all $c_{j}\leq u(t)$ , (35) can be established. Now we aggregate all $\lvert\phi_{j}(t)\rvert$ for which we could claim (35).

\lvert\phi(t)\rvert\leq\prod_{j:c_{j}\leq u(t)}\lvert\phi_{j}(t)\rvert\leq\exp\left(-r(1-r)\sum_{j:c_{j}\leq u(t)}\frac{c_{j}^{2}t^{2}}{4\sigma_{m}^{2}}\right).

(36)

Without loss of generality, we assume $A>1$ . Consequently, $u(t)\leq\sigma_{m}$ . Lemma A.3 implies for $\sigma_{m}\geq u(t)\geq 1$ , $\sum_{j:c_{j}\leq u(t)}c_{j}^{2}\geq u(t)\sigma_{m}/r(1-r)$ . Plugging this inequality into (36), we obtain

\lvert\phi(t)\rvert\leq\exp\left(-\frac{u(t)\sigma_{m}t^{2}}{4\sigma_{m}^{2}}\right)=\exp\left(-\frac{t}{8}\cdot\frac{2u(t)t}{\sigma_{m}}\right)\leq\exp\left(-\frac{t}{8}\right).

Therefore, for sufficiently large $A$ ,

\int_{A}^{\sigma_{m}/2}\left\lvert\phi(t)\right\rvert dt\leq\int_{A}^{\infty}\exp\left(-\frac{t}{8}\right)dt\leq\frac{e^{-A/8}}{8}\leq\frac{\varepsilon}{8}.

Thus we established (33) and the proof is complete. ∎

	$\displaystyle{\\|P^{t}(x,\cdot)-\pi(\cdot)\\|}_{\textsc{\tiny TV}}$	$\displaystyle=\sum_{y\in\Gamma:P^{t}(x,y)>\pi(y)}P^{t}(x,y)-\pi(y)$
		$\displaystyle\leq\sum_{y\in\Gamma_{0}:P^{t}(x,y)>\pi(y)}\pi(y)\left\|1-\frac{P^{t}(x,y)}{\pi(y)}\right\|+\sum_{y\notin\Gamma_{0}:P^{t}(x,y)>\pi(y)}P^{t}(x,y)\left\|1-\frac{\pi(y)}{P^{t}(x,y)}\right\|$
		$\displaystyle\leq\pi(\Gamma_{0})\max_{y\in\Gamma_{0}}\left\|1-\frac{P^{t}(x,y)}{\pi(y)}\right\|+P^{t}(x,\Gamma\setminus\Gamma_{0})$
		$\displaystyle\leq\max_{y\in\Gamma_{0}}\left\|1-\frac{P^{t}(x,y)}{\pi(y)}\right\|+\frac{1}{16},$