---
abstract: |
    In this paper we study metastable behaviour at low temperature of Glauber spin-flip dynamics on random graphs. We fix a large number of vertices and randomly allocate edges according to the Configuration Model with a prescribed degree distribution. Each vertex carries a spin that can point either up or down. Each spin interacts with a positive magnetic field, while spins at vertices that are connected by edges also interact with each other via a ferromagnetic pair potential. We start from the configuration where all spins point down, and allow spins to flip up or down according to a Metropolis dynamics at positive temperature. We are interested in the time it takes the system to reach the configuration where all spins point up. In order to achieve this transition, the system needs to create a sufficiently large droplet of up-spins, called critical droplet, which triggers the crossover.

    In the limit as the temperature tends to zero, and subject to a certain *key hypothesis* implying metastable behaviour, the average crossover time follows the classical *Arrhenius law*, with an exponent and a prefactor that are controlled by the *energy* and the *entropy* of the critical droplet. The crossover time divided by its average is exponentially distributed. We study the scaling behaviour of the exponent as the number of vertices tends to infinity, deriving upper and lower bounds. We also identify a regime for the magnetic field and the pair potential in which the key hypothesis is satisfied. The critical droplets, representing the saddle points for the crossover, have a size that is of the order of the number of vertices. This is because the random graphs generated by the Configuration Model are expander graphs.
address:
- 'Department of Mathematics, Ruhr University Bochum, Universitätsstraße 150, 44780 Bochum, Germany'
- 'Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands.'
- 'Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands.'
- 'Eindhoven University of Technology, Department of Mathematics and Computer Science, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.'
author:
- 'S. Dommers'
- 'F. den Hollander'
- 'O. Jovanovski'
- 'F.R. Nardi'
title: Metastability for Glauber dynamics on random graphs
---

[^1]

Introduction and main theorems
==============================

A physical system is in a *metastable state* when it remains locked for a very long time in a phase that is different from the one corresponding to thermodynamic equilibrium. The latter is referred to as the *stable state*. Classical examples are supersaturated vapours, supercooled liquids, and ferromagnets in the hysteresis loop. The main three objects of interest for metastability are the transition time from the metastable state to the stable state, the gate of configurations the system has to cross in order to achieve the transition, and the tube of typical trajectories the system follows prior to and after the transition.

Metastability for interacting particle systems on *lattices* has been studied intensively in the past three decades. Various different approaches have been proposed. After initial work by Cassandro, Galves, Olivieri and Vares [@CGOV84], Neves and Schonmann [@NS91], [@NS92], a powerful method – known as the *pathwise approach* to metastability based on large deviation theory – was developed in Olivieri and Scoppola [@OS95], [@OS96], Catoni and Cerf [@CC97], Manzo, Nardi, Olivieri and Scoppola [@MNOS04], Cirillo and Nardi [@CN13], Cirillo, Nardi and Sohier [@CNSo15]. This was successfully applied to low-temperature Ising and Blume-Capel models subject to Glauber spin-flip dynamics (in two and three dimensions, with isotropic, anisotropic and staggered interactions) in Kotecký and Olivieri [@KO92], [@KO93], [@KO94], Cirillo and Olivieri [@CO96], Ben Arous and Cerf [@BAC96], Nardi and Olivieri [@NO96]. Later, another powerful method – known as the *potential-theoretic approach* to metastability based on the analogy between Markov processes and electric networks – was developed in Bovier, Eckhoff, Gayrard and Klein [@BEGK00], [@BEGK01], [@BEGK02], [@BEGK04]. This was shown in Bovier and Manzo [@BM02], Bovier, den Hollander and Spitoni [@BdHS10] to lead to a considerable sharpening of earlier results. For other approaches to metastability, as well as further examples of metastable stochastic dynamics and relevant literature, we refer the reader to the monographs by Olivieri and Vares [@OV05], Bovier and den Hollander [@BdH15].

Recently, there has been interest in the Ising model on *random graphs* (Dembo and Montanari [@DM10], Dommers, Giardinà and van der Hofstad [@DGvdH10], Mossel and Sly [@MS13]). The only results known to date about metastability subject to Glauber spin-flip dynamics are valid for $r$-regular random graphs (Dommers [@Dpr]). In the present paper we investigate what can be said for more general degree distributions. Metastability is much more challenging on random graphs than on lattices. Moreover, we need to capture the metastable behaviour for a *generic realisation* of the random graph.

In Section \[IsingGlauber\] we define the Ising model on a random multigraph subject to Glauber spin-flip dynamics. We start from the configuration where all spins point down, and allow spins to flip up or down according to a Metropolis dynamics at positive temperature. We are interested in the time it takes the system to reach the configuration where all spins point up. In Section \[metastability\] we introduce certain geometric quantities that play a central role in the description of the metastable behaviour of the system, and state three general theorems that are valid under a certain key hypothesis. These theorems concern the average transition time, the distribution of the transition time, and the gate of saddle point configurations for the crossover, all in the limit of low temperature. They involve certain key quantities associated with the random graph. Our goal is to study the scaling behaviour of these quantities as the size of the graph tends to infinity.

In Section \[literature\] we describe four examples to which the three general theorems apply: three refer to regular lattices, while one refers to the Erdős-Rényi random graph. In Section \[configurationmodel\] we recall the definition of the Configuration Model, which is an example of a random graph with a non-trivial geometric structure. In Section \[maintheorems\] we state our main metastability results for the latter. In Section \[discussion\] we place these results in their proper context and give an outline of the remainder of the paper.

Ising model and Glauber dynamics {#IsingGlauber}
--------------------------------

Given a finite connected non-oriented multigraph $G=(V,E)$, let $\Omega=\{-1,+1\}^V$ be the set of configurations $\xi=\{\xi(v)\colon\,v \in V\}$ that assign to each vertex $v\in V$ a spin-value $\xi(v)\in\{-1,+1\}$. Two configurations that will be of particular interest to us are those where all spins point up, respectively, down: $$\boxplus \equiv +1, \qquad \boxminus \equiv -1.$$ For $\beta \geq 0$, playing the role of *inverse temperature*, we define the Gibbs measure $$\mu_\beta(\xi) = \frac{1}{Z_\beta}\,e^{-\beta {\mathcal{H}}(\xi)},
\qquad \xi\in\Omega,
\label{eq:Gibbs}$$ where ${\mathcal{H}}\colon\,\Omega\to{\mathbb{R}}$ is the *Hamiltonian* that assigns an energy to each configuration given by $${\mathcal{H}}(\xi) = -\frac{J}{2} \sum_{(v,w) \in E} \xi(v)\xi(w)
-\frac{h}{2} \sum_{v \in V} \xi(v), \qquad \xi\in\Omega,
\label{eq:hamiltonian}$$ with $J>0$ the *ferromagnetic pair potential* and $h>0$ the *magnetic field*. The first sum in the right-hand side of runs over all non-oriented edges in $E$. Hence, if $v,w \in V$ have $k \in {\mathbb{N}}_0$ edges between them, then their joint contribution to the energy is $-k\,\frac{J}{2}\,\xi(v)\xi(w)$.

We write $\xi\sim\zeta$ if and only if $\xi$ and $\zeta$ agree at all but one vertex. A transition from $\xi$ to $\zeta$ corresponds to a flip of a single spin, and is referred to as an *allowed move*. Glauber spin-flip dynamics on $\Omega$ is the continuous-time Markov process $(\xi_t)_{t \geq 0}$ defined by the transition rates $$c_\beta(\xi,\zeta) = \begin{cases}
e^{-\beta[{\mathcal{H}}(\zeta)-{\mathcal{H}}(\xi)]_+}, &\xi\sim\zeta,\\
0, &\mbox{otherwise}.
\end{cases}$$ The Gibbs measure in is the reversible equilibrium of this dynamics. We write $P^{G,\beta}_\xi$ to denote the law of $(\xi_t)_{t \geq 0}$ given $\xi_0=\xi$, ${\mathcal{L}}^{G,\beta}$ to denote the associated generator, and $\lambda^{G,\beta}$ to denote the principal eigenvalue of ${\mathcal{L}}^{G,\beta}$. The upper indices $G,\beta$ exhibit the dependence on the underlying graph $G$ and the interaction strength $\beta$ between neighbouring spins. For $A\subseteq\Omega$, we write $$\tau_A = \inf\big\{t>0\colon\,\xi_t \in A,\,\exists\,0<s<t\colon\,\xi_s \neq \xi_0\big\}$$ to denote the first hitting time of the set $A$ after the starting configuration is left.

Metastability
-------------

To describe the metastable behaviour of our dynamics we need the following geometric definitions.

\(a) The communication height between two distinct configurations $\xi,\zeta\in\Omega$ is $$\Phi(\xi,\zeta) = \min_{\gamma\colon\,\xi\to\zeta} \max_{\sigma\in\gamma}
{\mathcal{H}}(\sigma),$$ where the minimum is taken over all paths $\gamma\colon\,\xi\to\zeta$ consisting of allowed moves only. The communication height between two non-empty disjoint sets $A,B\subset\Omega$ is $$\Phi(A,B) = \min_{\xi\in A,\zeta\in B} \Phi(\xi,\zeta).$$ (b) The stability level of $\xi\in\Omega$ is $$V_\xi = \min_{ {\zeta\in\Omega:} \atop {{\mathcal{H}}(\zeta)<{\mathcal{H}}(\xi)} } \Phi(\xi,\zeta)-{\mathcal{H}}(\xi).$$ (c) The set of stable configurations is $$\Omega_{\mathrm{stab}}= \left\{\xi\in\Omega\colon\,{\mathcal{H}}(\xi)
= \min_{\zeta\in\Omega} {\mathcal{H}}(\zeta)\right\}.$$ (d) The set of metastable configurations is $$\Omega_{\mathrm{meta}}= \left\{\xi\in\Omega\backslash\Omega_{\mathrm{stab}}\colon\,
V_\xi = \max_{\zeta\in\Omega\backslash\Omega_{\mathrm{stab}}} V_\zeta\right\}.$$

It is easy to check that $\Omega_{\mathrm{stab}}= \{\boxplus\}$ for all $G$ because $J,h>0$. For general $G$, however, $\Omega_{\mathrm{meta}}$ is not a singleton, but we will be interested in those $G$ for which the following *hypothesis* is satisfied:

-   $\Omega_{\mathrm{meta}}= \{\boxminus\}$. \[itm:Hhyp\]

The energy barrier between $\boxminus$ and $\boxplus$ is $$\Gamma^\star = \Phi(\boxminus,\boxplus)-{\mathcal{H}}(\boxminus).$$

Let $({\mathcal{P}}^\star,{\mathcal{C}}^\star)$ be the unique maximal subset of $\Omega\times\Omega$ with the following properties (see Fig. [\[fig-protocrcr\]]{}):

1.  $\forall\,\xi\in{\mathcal{P}}^\star\,\exists\,\xi\prime\in{\mathcal{C}}^\star\colon\,\xi\sim\xi\prime$,\
    $\forall\,\xi\prime\in{\mathcal{C}}^\star\,\exists\,\xi\in{\mathcal{P}}^\star\colon\,\xi\prime\sim\xi$.

2.  $\forall\,\xi\in{\mathcal{P}}^\star\colon\,\Phi(\xi,\boxminus)<\Phi(\xi,\boxplus)$.

3.  $\forall\xi\,\in{\mathcal{C}}^\star\,\exists\,\gamma\colon\,\xi\to\boxplus\colon\,\\
    {\rm (i)} \max_{\zeta\in\gamma} {\mathcal{H}}(\zeta)-{\mathcal{H}}(\boxminus) \leq \Gamma^\star$.\
    [(ii)]{} $\gamma \cap\{\zeta\in\Omega\colon\,\Phi(\zeta,\boxminus)
    <\Phi(\zeta,\boxplus)\} = \emptyset$.

(15,15)(0,-1) [(0,0)(0,5)(0,10) (7,0)(7,5)(7,10) ]{} (-2,11)[${\mathcal{P}}^\star$]{} (5,11)[${\mathcal{C}}^\star$]{} (0.4,5.8)[$\xi$]{} (5.8,7.8)[$\xi\prime$]{} (-5,1.5)[$\boxminus$]{} (10.6,-2)[$\boxplus$]{} (-8.6,4.8)[$<\Gamma^\star+{\mathcal{H}}(\boxminus)$]{} (8.5,6)[$\leq \Gamma^\star+{\mathcal{H}}(\boxminus)$]{} (0,5) (7,7.2) (-4.5,3) (11,-.5) (0,5)[(3,1)[6.8]{}]{} (7,7.2)[(1,-2)[3.5]{}]{} (0,5)[(-2,-1)[3.5]{}]{}

Think of ${\mathcal{P}}^\star$ as the set of configurations where the dynamics, on its way from $\boxminus$ to $\boxplus$, is ‘almost at the top’, and of ${\mathcal{C}}^\star$ as the set of configurations where it is ‘at the top and capable over crossing over’. We refer to ${\mathcal{P}}^{\star}$ as the *protocritical set* and to ${\mathcal{C}}^\star$ as the *critical set*. Uniqueness follows from the observation that if $({\mathcal{P}}_1^\star,{\mathcal{C}}_1^\star)$ and $({\mathcal{P}}_2^\star,{\mathcal{C}}_2^\star)$ both satisfy conditions (1)–(3), then so does $({\mathcal{P}}_1^\star\cup{\mathcal{P}}_2^\star,{\mathcal{C}}_1^\star
\cup{\mathcal{C}}_2^\star)$. Note that $$\begin{array}{lll}
&{\mathcal{H}}(\xi)<\Gamma^\star+{\mathcal{H}}(\boxminus) &\forall\,\xi \in {\mathcal{P}}^\star,\\[0.1cm]
&{\mathcal{H}}(\xi)=\Gamma^\star+{\mathcal{H}}(\boxminus) &\forall\,\xi \in {\mathcal{C}}^\star.
\end{array}$$

It is shown in Bovier and den Hollander [@BdH15 Chapter 16] that *subject to hypothesis* (H) the following three theorems hold.

\[thm:critdrop\] $\lim_{\beta\to\infty} P^{G,\beta}_\boxminus(\tau_{{\mathcal{C}}^\star}<\tau_\boxplus
\mid \tau_\boxplus < \tau_\boxminus)=1$.

\[thm:nucltime\] There exists a $K^\star \in (0,\infty)$ such that $$\lim_{\beta\to\infty}
e^{-\beta\Gamma^\star}\,E^{G,\beta}_\boxminus(\tau_\boxplus) = K^\star.$$

\[thm:explaw\] (a) $\lim_{\beta\to\infty} \lambda^{G,\beta}_\beta\,E^{G,\beta}_\boxminus(\tau_\boxplus)=1$.\
(b) $\lim_{\beta\to\infty} P^{G,\beta}_\boxminus(\tau_\boxplus/
E^{G,\beta}_\boxminus(\tau_\boxplus)>t) = e^{-t}$ for all $t \geq 0$.

The proofs of Theorems \[thm:critdrop\]–\[thm:explaw\] in [@BdH15] do not rely on the details of the graph $G$, provided it is finite, connected and non-oriented (i.e., allowed moves are possible in both directions). For concrete choices of $G$, the task is to verify hypothesis (H) and to identify the triple (see Fig. \[fig-abstractdoublewell\]) $$\label{eq:triple}
\big({\mathcal{C}}^\star,\Gamma^\star,K^\star\big).$$ For lattice graphs this task has been carried out successfully (even for several classes of dynamics: see [@BdH15 Chapters 17–18]). For random graphs, however, the triplet in is random, and describing it represents a *very serious challenge*. In what follows we focus on a particular class of random graphs called the *Configuration Model*. But before doing so, we first summarise what is known in the literature.

(8,6)(0,0) (0,0)[(11,0)[11]{}]{} (0,0)[(0,9)[9]{}]{} (3.3,3.8)(3.3,1.9)(3.3,0) (4.8,5.6)(4.8,3)(4.8,0) (6.8,3.0)(6.8,1.5)(6.8,0) (0,5.8)(2.5,5.8)(4.8,5.8) [(2,8)(3,2)(4,5) (4,5)(5,7)(6,4) (6,4)(7,2)(8,5) ]{} (2.2,-1.3)[$\Omega_\mathrm{meta}$]{} (4.55,-.9)[${\mathcal{C}}^\star$]{} (5.8,-1.3)[$\Omega_\mathrm{stab}$]{} (11.5,-.3)[$\xi$]{} (-1.3,9.5)[${\mathcal{H}}(\xi)$]{} (-1.4,5.6)[$\Gamma^\star$]{} (3.3,4) (4.8,5.75) (6.8,3.20)

Examples of applications {#literature}
------------------------

### Torus

If the underlying graph is a torus, then the computations needed to identify the critical set ${\mathcal{C}}^\star$ and the prefactor $K^\star$ simplify considerably. As shown in Bovier and den Hollander [@BdH15 Chapter 17], for Glauber dynamics on a finite box $\Lambda\subset{\mathbb{Z}}^2$ (wrapped around to form a torus), the set ${\mathcal{C}}^\star$ consists of all $\ell_c \times (\ell_c -1)$ quasi-squares (located anywhere in $\Lambda$ in any of the two orientations) with an extra vertex attached to one of its longest sides, where $\ell_c = \lceil \tfrac{2J}{h}\rceil$ (the upper integer part of $\tfrac{2J}{h}$). Hypothesis (H) has been verified, and the exponent and the prefactor equal $$\Gamma^\star = J(4\ell_c)-h(\ell_c(\ell_c-1)+1), \qquad
K^\star = \frac{1}{|\Lambda|}\,\frac{1}{\frac{4}{3}(2\ell_c-1)}.$$ Metastable behaviour occurs if and only if $\ell_c \in (1,\infty)$, and for reasons of parity it is assumed that $\tfrac{2J}{h} \notin {\mathbb{N}}$. Similar results apply for a torus in ${\mathbb{Z}}^3$.

### Hypercube

For Glauber dynamics on the $n$-dimensional hypercube, Jovanovski [@Jpr] gives a complete description of the set ${\mathcal{C}}^\star$ (under the assumption that $\tfrac{h}{J}
\neq\frac{a}{b}$ for some $a\in \mathbb{N}$ and $b\in \left\lbrace 1,2,\ldots,2^{n}\right\rbrace$) and shows that $$\Gamma_n^\star = \tfrac{1}{3}\left(1-\tfrac{h}{J}+\left\lceil \tfrac{h}{J}\right\rceil \right)
\left(2^{\left\lceil n-\tfrac{h}{J}\right\rceil }-4+2\epsilon\right)-\epsilon, \qquad
K_n^\star = \frac{\left\lceil \tfrac{h}{J}\right\rceil !}{n!\,2^{n-4}\left(3-\epsilon\right)},$$ with $\epsilon=\left\lceil n-h\right\rceil \mbox{mod }2$. Hypothesis (H) has been verified.

### Complete graph

For Glauber dynamics on the complete graph $K_n$, it is easy to see that any monotone path from $\boxminus$ to $\boxplus$ is an optimal path. It is straightforward to show that ${\mathcal{C}}^\star=\{U\subseteq V\colon\,|U|=n^\star\}$ with $n^\star = \lceil\frac{1}{2}
(n-1-\tfrac{h}{J})\rceil$, whenever $\frac{h}{J}$ is not an integer, and to compute $$\label{GKexp}
\Gamma_n^\star=n^\star(J(n-n^\star)-h), \qquad  K_n^\star=\frac{1}{|{\mathcal{C}}^\star|}
\frac{n}{n-n^\star}.$$ Metastable behaviour occurs for any value of $h$ and $J$, provided $n$ is large enough. Hypothesis (H) is also easy to confirm by observing that every configuration lies on some optimal path. Like the hypercube, $K_n$ is an expander graph and consequently the communication height $\Gamma^\star$ grows at least linearly with the number of vertices (quadratically for $K_n$).

We can reduce the quadratic growth by introducing an interaction parameter that is inversely proportional to the size of the graph: e.g. $J=\tfrac{J'}{n}$ for some constant $J'>0$, with $h>0$ fixed. It follows that $$\Gamma_{n}^\star=n^\star\left(J'\left(\frac{n-n^\star}{n}-h\right)\right),$$ where this time $n^\star=\lceil\frac{n}{2}(1-\tfrac{h}{J'})-\frac{1}{2}\rceil$, and $K_n^\star$ is the same as in . Metastable behaviour occurs if and only if $\tfrac{h}{J'}
<1-\frac{1}{n}$.

### Erdős-Rényi random graph

Sharp results of the above type become infeasible when the graph is random. The Erdős-Rényi random graph is the result of performing bond percolation on the complete graph, and is a toy model of a graph with a random geometry. Let $\mathrm{ER}_n(p)$ denotes the resulting random graph on $n$ vertices with percolation parameter $p=f(n)/n$ for some $f(n)$ satisfying $\lim_{n\to\infty} f(n)
=\infty$, the so-called *dense* Erdős-Rényi random graph. Then, as shown in the appendix, metastable behaviour occurs for any $h,J>0$, and $$\lim_{n\to\infty} \frac{\Gamma_n^\star}{\tfrac14 Jnf(n)} = 1 \quad
\text{ in distribution under the law of }  \mathrm{ER}_n(f(n)/n),
\label{eq:er1}$$ which is accurate up to leading order. The computation of ${\mathcal{C}}_n^\star$ and $K_n^\star$, however, is a *formidable task*. The reason for this is that, while allows for a small error in the energy, the set ${\mathcal{C}}_n^\star$ is made up of configurations that have *exactly* the critical energy $\Gamma_n^\star$.

When $f(n)=\lambda$ for some constant $\lambda>1$, the *sparse case*, an analysis similar to the one carried out in this paper can be used to obtain lower and upper bounds on the communication height. However, we have been unable to prove a convergence of the form in .

Configuration Model {#configurationmodel}
-------------------

In this section we recall the construction of the random *multi-graph* known as the *Configuration Model* (illustrated in Fig. \[fig:CM\]). We refer to van der Hofstad [@vdHpr Chapter 7] for further details.

Fix $n\in{\mathbb{N}}$, and let $V=\{v_1,\ldots,v_n\}$. With each vertex $v_i$ we associate a *random degree* $D_i$, in such a way that $D_1,\ldots,D_n \in {\mathbb{N}}$ are i.i.d.with marginal probability distribution $f$ conditional on the event $\{\sum_{i=1}^n D_i
= \mbox{even}\}$. Consider a uniform matching of the elements in the set of *stubs* (also called half-edges), written $$\{x_{i,j}\}_{1 \leq i \leq n,1 \leq j \leq D_i}.$$ By erasing the second label of the stubs, we can associate with it a *multi-graph* ${\mathrm{CM}}_n$ satisfying the requirement that the degree of $v_i$ is $D_i$ for $1 \leq i \leq n$. The total number of edges is $\tfrac12\sum_{i=1}^n D_i$.

Throughout the sequel we use the symbol ${\mathbb{P}}_n$ to denote the law of the random multi-graph ${\mathrm{CM}}_n$ on $n$ vertices generated by the Configuration Model. To avoid degeneracies we assume that $${d_\mathrm{min}}= \min\{k\in{\mathbb{N}}\colon\,f(k)>0\} \geq 3,
\qquad {d_\mathrm{ave}}= \sum_{k\in{\mathbb{N}}} kf(k) < \infty,$$ i.e., all degrees are at least three and the average degree is finite. In this case the graph is connected *with high probability* (w.h.p.), i.e., with a probability tending to $1$ as $n\to\infty$ (see van der Hofstad [@vdHpr]).

Main theorems {#maintheorems}
-------------

We are interested in proving hypothesis (H) and identifying the key quantities in for $G = {\mathrm{CM}}_n$, which we henceforth denote by $({\mathcal{C}}^\star_n,\Gamma^\star_n,K^\star_n)$, in the limit as $n\to\infty$.

Our first main theorem settles hypothesis (H) for small magnetic field.

\[thm:hyp\] Suppose that the inequality in equation holds. Then $$\lim_{n\to\infty} {\mathbb{P}}_n\big({\mathrm{CM}}_n \text{ satisfies {\rm (H)}}\big) = 1.$$

Our second and third main theorem provide upper and lower bounds on $\Gamma^\star_n$. Label the vertices of the graph so that their degrees satisfy $d_{1}\leq\ldots\leq d_{n}$. Let $\gamma\colon\,\boxminus\to\boxplus$ be the path that successively flips the vertices $v_{1},\ldots,v_{n}$ (in that order), and let $\ell_{m}=\sum_{i=1}^{m}d_{i}$.

\[thm:Ubound\] Define $$\label{eq-defmbar}
\bar{m} = \min\left\{1 \leq m \leq n\colon\,\ell_m\left(1-\frac{\ell_m}{\ell_n}\right)
\geq \ell_{m+1}\left(1-\frac{\ell_{m+1}}{\ell_n}\right)-\frac{h}{J}\right\} < \frac{n}{2}.$$ Then, w.h.p., $$\Gamma_n^{\star} \leq \Gamma_n^+,
\qquad \Gamma_n^+ = J\ell_{\bar{m}}\Big(1-\frac{\ell_{\bar{m}}}{\ell_n}\Big)
-h\bar{m} \pm O\big(\ell_n^{3/4}\big).$$

For $0<x\leq\tfrac12$ and $\delta>1$, define (see Fig. \[fig:functionI\]) $$\begin{aligned}
I_{\delta}\left(x\right) &= \inf\Big\{0<y\leq x\colon\\
&1<x{}^{x\left(1-1/\delta\right)}
\left(1-x\right)^{\left(1-x\right)\left(1-1/\delta\right)}
\left(1-x-y\right)^{-\left(1-x-y\right)/2}\left(x-y\right)^{-\left(x-y\right)/2}y^{-y}\Big\}.
\end{aligned}
\label{eq:functionI}$$

(0,0) – (5,0) node\[anchor=north\] [$x$]{}; (0,0) – (0,4) node\[anchor=east\] [$I_{\delta}$]{}; (0,0) node\[anchor=north\] [0]{} (2,0) node\[anchor=north\] [$\tfrac{1}{4}$]{} (4,0) node\[anchor=north\] [$\tfrac{1}{2}$]{}; (0,1.4) node\[anchor=east\] [$\tfrac{11}{250}$]{} (0,2.8) node\[anchor=east\] [$\tfrac{11}{125}$]{}; plot \[smooth\] coordinates [(0,0) (1/5,30\*0.0111) (2/5,30\*0.0205) (3/5,30\*0.0286) (4/5,30\*0.0361) (5/5,30\*0.0429) (6/5,30\*0.0490) (7/5,30\*0.0546) (8/5,30\*0.0596) (9/5,30\*0.0641) (10/5,30\*0.0683) (11/5,30\*0.0721) (12/5,30\*0.0753) (13/5,30\*0.0780) (14/5,30\*0.0805) (15/5,30\*0.0825) (16/5,30\*0.0844) (17/5,30\*0.0854) (18/5,30\*0.0864) (19/5,30\*0.0869) (20/5,30\*0.0870)]{};

\[thm:Lbound\] Define $$\label{eq-defmtilde}
\tilde{m} = \min\left\lbrace 1 \leq m \leq n\colon\, \ell_m \geq \tfrac12\ell_n\right\rbrace.$$ Then, w.h.p., $$\Gamma_n^\star \geq \Gamma_n^-, \qquad
\Gamma_n^- = J\,d_\mathrm{ave}\,I_{d_\mathrm{ave}}
\left(\tfrac12\right) n - h\tilde{m} - o(n).
\label{eq:lboundGamma}$$

Under hypothesis [(H)]{} (or the weaker version of [(H)]{} introduced in Section \[althyp\]), Theorems [\[thm:Ubound\]–\[thm:Lbound\]]{} yield the following bounds on the crossover time (see Dommers [@Dpr Proposition 2.4]): $$\label{timesandwich}
\lim_{\beta\to\infty} P_{\boxminus}^{G,\beta}\left(e^{\Gamma_n^- -\varepsilon}
\leq \tau_\boxplus \leq e^{\Gamma_n^+ +\varepsilon}\right) =1.$$

In Corollary \[cor:mvalues\] we compute $\bar{m}$, $\ell_{\bar{m}}$, $\tilde{m}$ for two degree distributions: Dirac distributions and power-law distributions. It is clear that $\tilde{m}=\lceil \tfrac12 n\rceil$ for Dirac distributions.

The bounds we have found in Theorems \[thm:Ubound\]–\[thm:Lbound\] are tight in the limit of large degrees. Indeed, by the law of large numbers we have that $$\ell_{n}\frac{\ell_{\bar{m}}}{\ell_{n}}
\left(1-\frac{\ell_{\bar{m}}}{\ell_{n}}\right)
\leq\tfrac{1}{4}\ell_{n}=\tfrac{1}{4} d_{\mathrm{ave}}\,n\left[1+o(1)\right].$$ Hence $$\frac{\Gamma_n^+}{\Gamma_n^-}
= \frac{\frac{1}{4}d_{\mathrm{ave}}\left[1+o\left(1\right)\right]
-\frac{h}{J}\frac{\bar{m}}{n}+o(1)}{d_{\mathrm{ave}}
I_{d_{\mathrm{ave}}}\left(\frac{1}{2}\right)-\frac{h}{J}\frac{\tilde{m}}{n}
-o(1)}.
\label{eq:ratioofbounds}$$ In the limit as $d_{\mathrm{ave}}\to\infty$ we have $I_{d_{\mathrm{ave}}}
\left(\frac{1}{2}\right)\to\frac{1}{4}$, in which case tends to 1.

Discussion
----------

We close this introduction by discussing our main results.

[**1.**]{} We believe that Theorem \[thm:hyp\] holds as soon as $$0 < h < (d_\mathrm{min}-1)J,$$ i.e., we believe that in the limit as $\beta\to\infty$ followed by $n\to\infty$ this choice of parameters corresponds to the *metastable regime* of our dynamics, i.e., the regime where $(\boxminus,\boxplus)$ is a *metastable pair* in the sense of [@BdH15 Chapter 8].

[**2.**]{} The scaling behaviour of $\Gamma_n^\star$ as $n\to\infty$, as well as the geometry of ${\mathcal{C}}_n^\star$ are hard to capture. We can only offer some conjectures.

\[conj:scalnucltime\] There exists a $\gamma^\star \in (0,\infty)$ such that $$\lim_{n\to\infty} {\mathbb{P}}_n\Big( \big| n^{-1} \Gamma^\star_n - \gamma^\star\big|
> \delta\Big) = 0 \qquad \forall\,\delta>0.$$

\[conj:scalcritdrop\] There exists a $c^\star \in (0,1)$ such that $$\lim_{n\to\infty} {\mathbb{P}}_n\Big( \big| n^{-1} \log|{\mathcal{C}}^\star_n| - c^\star\big|
> \delta\Big) = 0 \qquad \forall\,\delta>0.$$

\[conj:scalprefac\] There exists a $\kappa^\star \in (1,\infty)$ such that $$\lim_{n\to\infty} {\mathbb{P}}_n\Big( \big| |{\mathcal{C}}^\star_n|\,K^\star_n - \kappa^\star\big|
> \delta\Big) = 0 \qquad \forall\,\delta>0.$$

As is clear from the results mentioned in Section \[literature\], all three conjectures are true for the torus, the hypercube and the complete graph. This supports our belief that they should be true for a large class of random graphs as well.

[**3.**]{} In Section \[CMdynamic\] we will give a *dynamical construction* of ${\mathrm{CM}}_n$ in which vertices are added one at a time and edges are relocated. This leads to a *random graph process* $({\mathrm{CM}}_n)_{n\in{\mathbb{N}}}$ whose marginals respect the law of the Configuration Model. In Section \[tailprop\] we will show that this process is *tail trivial*, i.e., all events in the tail sigma-algebra $${\mathcal{T}}= \cap_{N \in {\mathbb{N}}}\, \sigma\left(\cup_{n \geq N} {\mathrm{CM}}_n\right)$$ have probablity 0 or 1. Consequently, the associated communcation height process $(\Gamma^\star_n)_{n\in{\mathbb{N}}}$ with $\Gamma^\star_n = \Gamma^\star({\mathrm{CM}}_n)$ is tail trivial as well. In particular, both $\gamma^*_- = \liminf_{n\to\infty} n^{-1}
\Gamma^\star_n$ and $\gamma^*_+ = \limsup_{n\to\infty} n^{-1} \Gamma^\star_n$ exists and are constant a.s. Theorems \[thm:Ubound\]–\[thm:Lbound\] show that $0<\gamma^*_- \leq \gamma^*_+<\infty$. Settling Conjecture \[conj:scalnucltime\] amounts to showing that $\gamma^*_-=\gamma^*_+$.

[**4.**]{} It was shown by Dommers [@Dpr] that for the Configuration Model with $f=\delta_r$, $r \in {\mathbb{N}}\backslash\{1,2\}$, i.e., for a random regular graph with degree $r$, there exist constants $0<\gamma_-^\star(r)<\gamma_+^\star(r)<\infty$ such that $$\label{eq:sandwich}
\lim_{n\to\infty} \lim_{\beta\to\infty}
{\mathbb{E}}_n\left( P^{{\mathrm{CM}}_n}_\boxminus\left( e^{\beta n\gamma_-^\star(r)}
\leq \tau_\boxplus \leq e^{\beta n\gamma_+^\star(r)}\right) \right) = 1,$$ provided $\frac{h}{J} \in (0,C_0\sqrt{r})$ for some constant $C_0 \in (0,\infty)$ that is small enough. Moreover, there exist constants $C_1 \in (0,\tfrac14\sqrt{3})$ and $C_2 \in
(0,\infty)$ (depending on $C_0$) such that $$\gamma_-^\star(r) \geq \tfrac14 Jr - C_1J\sqrt{r}, \qquad
\gamma_+^\star(r) \leq \tfrac14 Jr + C_2J\sqrt{r}, \qquad r \in {\mathbb{N}}\backslash\{1,2\}.$$ The result in is derived without hypothesis (H), but it is shown that hypothesis (H) holds as soon as $r \geq 6$.

[**Outline.**]{} The rest of the paper is organised as follows. In Section \[metstate\] we prove that hypothesis (H) holds under certain constraints on the magnetic field $h$ and the minimal degree of the graph $d_\mathrm{min}$. Section \[althyp\] gives an alternative to hypothesis (H), which holds for a broader range parameters, yet still permits us to claim our bounds on the crossover time. In Section \[thmproofs\] we prove our upper and lower bounds on $\Gamma_n^\star$. Part of this proof depends on a *dynamical construction* of ${\mathrm{CM}}_n$. In Section \[tailprop\] we derive certain properties of this construction.

Proof of Theorem \[thm:hyp\] {#metstate}
============================

This section gives a proof of hypothesis (H). We start with the following remark about the configurations in $\Omega$.

[A natural isomorphism between configurations and subsets of vertices of the underlying graph $G=(V,E)$ comes from identifying $\xi\in\Omega$ with the set $\{v \in V\colon\,\xi(v)=+1\}$. With this in mind, we denote by $\overline{\xi}$ the configuration corresponding to the complement of this set: $\{v\in V\colon\,\xi(v)=-1\}$. Furthermore, for $\zeta,\sigma\in\Omega$ we denote by $E(\zeta,\sigma) \subseteq E$ the set of all unoriented edges $\{(v,w)\in E\colon\,\zeta(v)=\sigma(w)=+1\}$. The main use of the last definition will be for $\sigma=\overline{\zeta}$: $E(\zeta,\overline{\zeta})$ is the edge boundary of the set $\{v\in V\colon\,\zeta(v)=+1\}$.]{}

We next give two lemmas that will be useful later on.

\[lem:Ideltabound\] For all $\delta \geq 2$ and $0<x\leq\tfrac12$, $I_{\delta}\left(x\right) \leq \left(1-x\right)
-\left(1-x\right)^{2\left(1-1/\delta\right)}$.

The claim can be verified numerically. For $w \in \left(0,\frac{1}{2}\right]$, let $\tilde{y}
=\left(1-x\right)-\left(1-x\right)^{2\left(1-w\right)}$. Fig. \[fig:cplot\] gives a contour plot of the function $$\tilde{I}\left(x,w\right) = x^{x\left(1-w\right)}\left(1-x\right)^{\left(1-x\right)
\left(1-w\right)}\left(1-x-\tilde{y}\right)^{-\left(1-x-\tilde{y}\right)/2}
\left(x-\tilde{y}\right)^{-\left(x-\tilde{y}\right)/2}\tilde{y}^{-\tilde{y}}.$$

\[htbp\]

Note that $\tilde{I}\left(x,w\right)\geq 1$, which immediately implies Lemma \[lem:Ideltabound\] when we take $w=1/\delta$. It is easy to verify that the boundary values corresponding to $x \downarrow 0$ and $x \uparrow 1$ result in $\tilde{I}\left(x,w\right) \downarrow 1$.

\[lem:Ideltamonotone\] The function $x\rightarrow\frac{I_{\delta}\left(x\right)}{x}$ is non-increasing on $\left(0,\frac{1}{2}\right]$.

By definition of $I_{\delta}\left(x\right)$, the function $$\hat{I}\left(x,z\right) = x^{x\left(1-1/\delta\right)}\left(1-x\right)^{\left(1-x\right)
\left(1-1/\delta\right)}\left(1-x-xz\right)^{-\left(1-x-xz\right)/2}
\left(x-xz\right)^{-\left(x-xz\right)/2}\left(xz\right)^{-xz}$$ satisfies $\hat{I}(x,\frac{I_{\delta}\left(x\right)}{x})=1$ for all $x\in\left(0,\frac{1}{2}\right]$. It will therefore suffice to show that $$\label{Itask}
\frac{\partial}{\partial x}\vert_{z=\frac{I_{\delta}\left(x\right)}{x}} \hat{I}\left(x,z\right) \geq 0,$$ since this implies that, for $\epsilon$ sufficiently small, $\hat{I}(x+\epsilon,\frac{I_{\delta}
\left(x\right)}{x})\geq1$, and hence that $$\inf\left\{w\colon\,\hat{I}\left(x+\epsilon,w\right)\geq1\right\} \leq\frac{I_{\delta}\left(x\right)}{x},$$ and thus $\frac{I_{\delta}(x+\epsilon)}{x+\epsilon} \leq \frac{I_{\delta}\left(x\right)}{x}$. Observe that $$\begin{aligned}
&\frac{\partial}{\partial x}\hat{I}\left(x,z\right)\\
&= \hat{I}\left(x,z\right)
\left\{ \log\left(\left(\frac{x}{1-x}\right)^{\left(1-1/\delta\right)}
\left(1-x-xz\right)^{\left(1+z\right)/2}\left(x-xz\right)^{-\left(1-z\right)/2}
\left(xz\right)^{-z}\right)\right\}.
\end{aligned}$$ For $z=\frac{I_{\delta}\left(x\right)}{x}$, $\hat{I}\left(x,z\right)=1$ implies $$\left(x^{x\left(1-1/\delta\right)}\left(1-x\right)^{\left(1-x\right)
\left(1-1/\delta\right)}\right)^{\frac{1}{x}}=\left(1-x-xz\right)^{\frac{1}{2x}
-\left(1+z\right)/2}\left(x-xz\right)^{\left(1-z\right)/2}\left(xz\right)^{z}$$ and hence $$\begin{aligned}
&\frac{\partial}{\partial x}\hat{I}\left(x,z\right)\\
&=\hat{I}\left(x,z\right)\left\{ \log\left(\left(\frac{x}{1-x}\right)^{\left(1-1/\delta\right)}
\left(x^{x\left(1-1/\delta\right)}\left(1-x\right)^{\left(1-x\right)
\left(1-1/\delta\right)}\right)^{-\frac{1}{x}}\left(1-x-xz\right)^{\frac{1}{2x}}\right)\right\}.
\label{eq:derivIhat}
\end{aligned}$$ The term inside the logarithm in (\[eq:derivIhat\]) simplifies to $\left(1-x\right)^{-\frac{1}{x}
\left(1-1/\delta\right)}\left(1-x-xz\right)^{\frac{1}{2x}}$, which satisfies $\left(1-x\right)^{-\frac{1}{x}\left(1-1/\delta\right)}\left(1-x-xz\right)^{\frac{1}{2x}}\geq1$ whenever $1-x-\left(1-x\right)^{2\left(1-1/\delta\right)} \geq xz=I_{\delta}\left(x\right)$. By Lemma \[lem:Ideltabound\], this is true for all $x\in\left(0,\frac{1}{2}\right]$, and so follows.

We can now proceed with the proof of hypothesis (H). Let $\sigma\in\Omega$ be any configuration that satisfies $x=\ell_{\sigma}/\ell_n\leq\tfrac12$, where $\ell_\sigma
=\sum_{i\in\sigma} d_i$. We will construct a path from $\sigma$ to some $\sigma\prime
\in\Omega$ satisfying $\mathcal{H}\left(\sigma\prime\right)<\mathcal{H}\left(\sigma\right)$ by removing one vertex at a time, obtaining a path $\sigma=\sigma_{0},\ldots,\sigma_{m}
=\sigma\prime$. In particular, at step $t$ we remove any vertex $v_{t}\in\sigma_{t-1}$ that minimises the quantity $\left|E\left(v_{t},\sigma_{t-1}\backslash v_{t}\right)\right|
-\left|E\left(v_{t},\overline{\sigma_{t-1}}\right)\right|$. It will follow that for every $\sigma_{i}$ in this path, we have $\left|\mathcal{H}\left(\sigma_{i}\right)-\mathcal{H}\left(\sigma_{0}
\right)\right|<\Gamma^{\star}$, which proves the claim of the theorem.

The probability that some configuration $\sigma$, chosen uniformly from all configurations in $\Omega$ with $\ell_\sigma=L$, has a boundary of size $\left|E\left(\sigma,
\overline{\sigma}\right)\right|=K$ equals $$\begin{aligned}
&{L \choose K}K!\left(L-K-1\right)!!{\ell_{n}-L \choose K}
\left(\ell_{n}-L-K-1\right)!!/\left(\ell_{n}-1\right)!! \\
&\approx \frac{\left(L\right)!}{\left(L-K\right)!!}
\frac{\left(\ell_{n}-L\right)!}{K!\left(\ell_{n}-L-K\right)!!}\frac{1}{\ell_{n}!!} \\
&\approx  L^L\left(\ell_{n}-L\right)^{\left(\ell_{n}-L\right)}
\left(\ell_{n}-L-K\right)^{-\left(\ell_{n}-L-K\right)/2}
\left(L-K\right)^{-\left(L-K\right)/2}K^{-K}\ell_{n}^{-\ell_{n}/2},
\end{aligned}$$ where the symbol $\approx$ stands for equality up to polynomial terms (here of order $O(n^{2})$). Let $x=L/\ell_{n}$ and $y=K/\ell_{n}$, so that the above expression becomes $$\exp\left[\ell_{n}\log\left(x{}^{x}\left(1-x\right)^{\left(1-x\right)}
\left(1-x-y\right)^{-\left(1-x-y\right)/2}\left(x-y\right)^{-\left(x-y\right)/2}y^{-y}\right)\right].$$ Furthermore, if we define $\eta\left(x\right)$ by $$\label{eq:defeta}
\exp\left[\ell_{n}\log\eta\left(x\right)\right]
=\left|\left\{ U\subseteq V\colon\,\ell_U=\ell_{n}x\right\} \right|,$$ then the probability of there being any configuration of total degree $L$ having a boundary size $K$ is bounded from above by $$\label{sd-expbound}
\exp\left[\ell_{n}\log\left(\eta\left(x\right)x{}^{x}\left(1-x\right)^{\left(1-x\right)}
\left(1-x-y\right)^{-\left(1-x-y\right)/2}\left(x-y\right)^{-\left(x-y\right)/2}y^{-y}\right)\right].$$

It is easy to see that, by using $\delta=d_{\min}$, the cardinality in the right-hand side of is bounded from above by ${\ell_{n}/\delta \choose x\ell_{n}/\delta}$. Using Stirling’s approximation for this term, and substituting in , we get $$\label{eq:probineq}
\begin{aligned}
&\mathbb{P}\left[\exists\, A\subseteq V\colon\,\ell_{A}=x\ell_{n}
\mbox{ and }\left|E\left(A,\overline{A}\right)\right|=y\ell_{n}\right]\\
&\leq \exp\left[\ell_{n}\log\left(x{}^{x\left(1-1/\delta\right)}
\left(1-x\right)^{\left(1-x\right)\left(1-1/\delta\right)}
\left(1-x-y\right)^{-\left(1-x-y\right)/2}\left(x-y\right)^{-\left(x-y\right)/2}y^{-y}\right)\right].
\end{aligned}$$ Recall the definition of $I_{\delta}$ from and note that is exponentially small for $y<I_{\delta}\left(x\right)$, and by a union bound it is exponentially small for all such $y$.

Suppose that after $s$ vertices have been removed, we reach a configuration $\sigma_{s}$ with $\mathcal{H}\left(\sigma_{s}\right) < \mathcal{H}\left(\sigma\right)$, such that for every vertex $v\in\sigma_{s}$ we have $$\left|E\left(v,\sigma_{s}\backslash v\right)\right|+\frac{h}{J}
>\left|E\left(v,\overline{\sigma_{s}}\right)\right|.
\label{eq:afters}$$ In other words, equation (\[eq:afters\]) states that after removing $s$ vertices we are at a configuration of lower energy, and removing any additional vertex leads to a configuration of higher energy. Note that if no such $s$ exists, then we keep on removing vertices until $\boxminus$ has been reached. By the assumption that $h$ is sufficiently small (by , it would suffice if $h<\tfrac12\,
J\,d_\mathrm{ave}\,I_{d_\mathrm{ave}} \left(\tfrac12\right) \frac{n}{\tilde{m}}$, where $\tilde{m}$ was also defined in the aforementioned equation), w.h.p., every configuration $\sigma$ of total degree $\ell_{\sigma}\leq\tfrac12 \ell_n$ satisfies $\mathcal{H}
\left(\sigma\right)>\mathcal{H}\left(\boxminus\right)$. If $v\in\sigma_{s}$ has no self-loops, then we have $$\left|E\left(v,\sigma_{s}\backslash v\right)\right|
=d_{v}-\left|E\left(v,\overline{\sigma_{s}}\right)\right|$$ and thus the condition in is satisfied when for all $v\in\sigma_{s}$, $$\label{eq:}
\tfrac12\left(d_{v}+\frac{h}{J} \right) > \left|E\left(v,\overline{\sigma_{s}}\right)\right|.$$ The total number of vertices with self-loops is w.h.p. of order $o(n)$, and so it will be evident from the bounds below that this assumption is immaterial. The second inequality in $$\left|E\left(\sigma_{s},\overline{\sigma_{s}}\right)\right|
< \tfrac12 \sum_{v\in\sigma_{s}} \left( d_{v}+\frac{h}{J}  \right)
= \tfrac12 \bigg(x\ell_{n}-\sum_{i=1}^{s}d_{i}+\frac{h\left(\left|\sigma\right| -s\right)}{J}  \bigg)
\leq\left|E\left(\sigma,\overline{\sigma}\right)\right|$$ holds whenever $$x\ell_{n}-2\left|E\left(\sigma,\overline{\sigma}\right)\right|+\frac{h\left(\left|\sigma\right| -s\right)}{J}
\leq \sum_{i=1}^{s} d_{i},$$ which in particular is true when we take the smallest $s$ such that $$\sum_{i=1}^{s} d_{i} \geq x\ell_{n}-2I_{\delta}\left(x\right)\ell_{n}
+\frac{h\left(\left|\sigma\right| -s\right)}{J}.
\label{eq:condits}$$ Furthermore, by removing $s$ vertices, the change in the size of the boundary at step $t$ is given by $$\begin{aligned}
&\left|E\left(\sigma_{t},\overline{\sigma_{t}}\right)\right|
-\left|E\left(\sigma,\overline{\sigma}\right)\right|
= \sum_{i=1}^{t}\big(\left|E\left(v_{i},\sigma_{i-1}\backslash v_{i}\right)\right|
-\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|\big)\\
&\qquad \leq \sum_{i=1}^{t}\left(d_{i}-2\left\lceil d_{i}\,
\frac{I_{\delta}\left(x\right)}{x}\right\rceil \right)
\leq \left(1-2\,\frac{I_{\delta}\left(x\right)}{x}\right)\sum_{i=1}^{t} d_{i}.
\label{eq:stepssum}
\end{aligned}$$ The first inequality in follows from the following observation: note that w.h.p. $|E(\sigma,\overline{\sigma})|$ $\geq I_{\delta}(x)\ell_n$, and hence the “proportion” of the total degree of $\sigma$ that is paired with vertices in $\overline{\sigma}$ is at least $I_{\delta}(x)/x$. This implies that there must be some vertex $v_i$ with a proportion of at least $I_{\delta}(x)/x$ of its degree connected with vertices in $\overline{\sigma}$. In other words, $v_i$ shares at least $\lceil d_i \frac{I_{\delta}(x)}{x}\rceil$ edges with $\overline{\sigma}$.

By the definition of $s$, we that $|E(\sigma,\overline{\sigma})|=|E(\sigma_s,\overline{\sigma_s})|
+o(n)$ (when $d_s=o(n)$), and hence dropping the $o(n)$-term is of no consequence in the following computations. This implies that if $t$ is such that $|E(\sigma_t,\overline{\sigma_t})|
-|E(\sigma,\overline{\sigma})|$ is maximised, then we get (again, possibly after dropping a term of order $o(n)$) $$\begin{aligned}
\sum_{i=1}^t \big(\left|E\left(v_{i},\sigma_{i-1}\right)\right|
-\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|\big)
& = & \sum_{i=t+1}^s \big(\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|
-\left|E\left(v_{i},\sigma_{i-1}\right)\right|\big).
\label{eq:peakequality}
\end{aligned}$$ Let $m_{t}$ denote the left-hand side of $\eqref{eq:peakequality}$, so that $$\begin{aligned}
m_{t} &= \sum_{i=1}^{t}\left(d_{i}-2\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|\right)
=  \sum_{i=t+1}^{s}\left(d_{i}-2\left|E\left(v_{i},\sigma_{i-1}\right)\right|\right)\\
&=  \sum_{i=1}^{s}\left(d_{i}-2\left|E\left(v_{i},\sigma_{i-1}\right)\right|\right)
-\sum_{i=1}^{t}\left(d_{i}-2\left|E\left(v_{i},\sigma_{i-1}\right)\right|\right).
\end{aligned}$$ Hence $$\sum_{i=1}^{t}d_{i}\left(\frac{\sum_{i=1}^{t}\left(d_{i}
-2\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|\right)}{\sum_{i=1}^{t}d_{i}}+1\right)
=\sum_{i=1}^{s}d_{i}-\sum_{i=t+1}^{s}2\left|E\left(v_{i},\sigma_{i-1}\right)\right|,$$ and thus $$\begin{aligned}
m_{t} &=  \left(\frac{\sum_{i=1}^{t}\left(d_{i}
-2\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|\right)}
{\sum_{i=1}^{t}d_{i}}\right)\left(\frac{\sum_{i=1}^{t}\left(d_{i}
-2\left|E\left(v_{i},\overline{\sigma_{i-1}}\right)\right|\right)}
{\sum_{i=1}^{t}d_{i}}+1\right)^{-1}\\
&\qquad\qquad\qquad \times \left(\sum_{i=1}^{s}d_{i}
-\sum_{i=t+1}^{s}2\left|E\left(v_{i},\sigma_{i-1}\right)\right|\right)\\
&\leq \frac{1}{2}\left(1-2\frac{I_{\delta}\left(x\right)}{x}\right)
\left(1-\frac{I_{\delta}\left(x\right)}{x}\right)^{-1}\left(x\ell_{n}
-2I_{\delta}\left(x\right)\ell_{n}+\frac{h\left(\left|\sigma\right|-s\right)}{J}\right),
\end{aligned}$$ where for the last inequality we use – and the monotonicity of $y\rightarrow y(y+1)^{-1}$. From , using the fact that $nd_{\mathrm{ave}}=\ell_{n}+o\left(n\right)$, we get that $ \mathcal{H}\left(\sigma_{t}\right) - \mathcal{H}\left(\sigma\right) < \Gamma^{\star}$ whenever $$\frac{h}{J\ell_{n}}\left(2\tilde{m}+t+\left(\left|\sigma\right|
-s\right)\left(\frac{x-2I_{\delta}\left(x\right)}{x-I_{\delta}\left(x\right)}\right)\right)
<2I_{d_{\mathrm{ave}}}\left(\tfrac{1}{2}\right)
-\left(x-2I_{\delta}\left(x\right)\right)^{2}\left(x-I_{\delta}\left(x\right)\right)^{-1}.
\label{eq:ihalfbound}$$ Note that if $x<2I_{\delta}\left(x\right)$, then for sufficiently small $h$ we can find a monotone downhill path to $\boxminus$. More precisely, $x<2I_{\delta}\left(x\right)$ implies that the terms in the right-hand side of become negative, and hence for $\frac{h}{J}<d_{\min}(\frac{2I_{\delta}\left(x\right)}{x}-1)$ every step in our path is a downhill step. For $x\geq2I_{\delta}\left(x\right)$, observe first that since the function $u\rightarrow\frac{\left(1-2u\right)^{2}}{\left(1-u\right)}$ is non-increasing for $u\leq\frac{1}{2}$, by Lemma \[lem:Ideltamonotone\] $$\frac{\left(x-2I_{\delta}\left(x\right)\right)^{2}}{\left(x-I_{\delta}\left(x\right)\right)}
= x\frac{(1-2\frac{I_{\delta}\left(x\right)}{x})^{2}}{(1-\frac{I_{\delta}\left(x\right)}{x})}
\leq \tfrac{1}{2}\frac{(1-4I_{\delta}(\tfrac{1}{2}))^{2}}
{(1-2I_{\delta}\left(\tfrac{1}{2}\right))},$$ and thus a sufficient condition for to hold is $$\tfrac{h}{J}\left(\tfrac{1}{d_{\mathrm{ave}}} + \tfrac{1}{2} \right)
< 2I_{d_{\mathrm{ave}}}\left(\tfrac{1}{2}\right)
-\tfrac{1}{2}\left(1-4I_{d_{\mathrm{min}}}\left(\tfrac{1}{2}\right)\right)^{2}
\left(1-2I_{d_{\mathrm{min}}}\left(\tfrac{1}{2}\right)\right)^{-1}.
\label{eq:Hcond1}$$ Hence we have a path $\sigma \to \sigma_{s}$ (or, when such an $s$ satisfying does not exist, a path $\sigma \to \boxminus$) with $\mathcal{H}\left(\sigma_{s}\right)
< \mathcal{H}\left(\sigma\right)$ that never exceeds $\mathcal{H}\left(\sigma\right)$ by $\Gamma^{\star}$ or more, whenever $h$ is sufficiently small and holds. This proves the claim of the theorem for all configurations $\sigma$ with $\ell_{\sigma}
\leq \tfrac12\ell_n$.

Note also that, for $\ell_{\sigma} > \tfrac12\ell_n$, the same argument can be repeated by adding a vertex at each step, which will also come at a lower cost since at each step the magnetisation changes by $-h$.

An alternative to hypothesis (H) {#althyp}
================================

In this section gives a weaker version of hypothesis (H), which nonetheless suffices as a prerequisite for Theorem \[thm:nucltime\]. This weaker version can be verified for a parameter range that is larger than the one needed in Section \[metstate\].

We can repeat the arguments given in Section \[metstate\]. But, instead of insisting that $\mathscr{V}_{\sigma}<\Gamma^{\star}$ for every configuration $\sigma \in \Omega$, we require that $\mathscr{V}_{\sigma}$ is bounded from above by our upper bound on $\Gamma^{\star}$, since this guarantees that our upper bound on the crossover time is still valid and still holds (see Dommers [@Dpr Lemma 5.3]). Thus, it follows from the arguments leading to that we only need the condition $$\frac{h}{J\ell_{n}}\left(\bar{m}+t+\left|\sigma\right|
-s\left(\frac{x-2I_{\delta}\left(x\right)}{x-I_{\delta}\left(x\right)}\right)\right)
\leq 2\frac{\ell_{\bar{m}}}{\ell_n}\Big(1-\frac{\ell_{\bar{m}}}{\ell_n}\Big)
-\left(x-2I_{\delta}\left(x\right)\right)^{2}\left(x-I_{\delta}\left(x\right)\right)^{-1}.
\label{eq:ihalfbound2}$$ For $h$ sufficiently small, the ratio $\frac{\ell_{\bar{m}}}{\ell_n}$ can be made arbitrarily close to $\tfrac12$, in which case the right-hand side of becomes strictly positive. This implies that the inequality in holds for any $\delta \geq 3$ whenever $h$ is sufficiently small.

Proof of Theorems \[thm:Ubound\] and \[thm:Lbound\] {#thmproofs}
===================================================

A dynamic construction of the configuration model {#CMdynamic}
-------------------------------------------------

Prior to giving the proof of Theorems \[thm:Lbound\] and \[thm:Ubound\], we introduce a *dynamical construction* of the CM graph. This will be used to obtain the upper bound in Theorem \[thm:Ubound\].

Let $V=\{v_{i}\} _{i=1}^{n}$ be a sequence of vertices with degrees $\{d_{i}\} _{i=1}^{n}$. In this section we construct a graph $G=(V,E)$ with the same distribution as a graph generated through the Configuration Model algorithm, but in a *dynamical way*, as follows.

Suppose that $\xi_{m}$ is a uniform random matching of the integers $\{1,\ldots,2m\} $, denoted by $\xi_{m}=\{(x_{1},x_{2}),\ldots,(x_{2m-1},
x_{2m}\}$, where the pairs are listed in the order they were created (which is not an important issue, so long as we agree on some labeling). Next, let $u$ be uniform on $\{1,\ldots,2m,2m+1\} $ and set $\xi_{m+1}
=\xi_{m}\cup\{(2m+2,u)\}$ if $u=2m+1$. Else if $u \neq 2m+1$, then w.l.o.g.$u=x_{2i-1}$ for some $i\leq m$, and we set $\xi_{m+1}=\{\xi_{m}\backslash
\{(x_{2i-1},x_{2i})\}\}\cup\{(2m+2,x_{2i-1}),(2m+1,x_{2i})\}$. Then $\xi_{m+1}$ is a uniform matching of the points $\{1,\ldots,2m,2m+2\}$. It is now obvious how the construction of $G$ follows from the given scheme.

Energy estimates
----------------

Label the vertices of the graph so that their degrees satisfy $d_{1}\leq\ldots\leq
d_{n}$. Let $\gamma\colon\,\boxminus\to\boxplus$ be the path that successively flips the vertices $v_{1},\ldots,v_{n}$ (in that order), and let $\ell_{m}=\sum_{i=1}^{m}
d_{i}$. We show that, w.h.p., for every $1\leq m\leq n$, $$\mathcal{H}\left(\gamma_{m}\right)-\mathcal{H}\left(\boxminus\right)
=J\ell_{m}\Big(1-\frac{\ell_{m}}{\ell_{n}}\Big)-mh \pm O\big(\ell_{n}^{3/4}\big).
\label{eq:pathbound}$$

We are particularly interested in the maximum of over all $1\leq m \leq n$. To this avail, observe that the function defined by $$g\left(x\right) = Jx\left(1-x\right)-h\left(x\right)
\label{eq:functiong}$$ has at most one maximum for $x\in[0,1]$ if $x \mapsto h(x)$ is non-decreasing. Thus, taking $x=\frac{\ell_{m}}{\ell_{n}}$ and $h(x)=hx\frac{m}{\ell_{m}}$, we see that our definition of $\bar{m}$ in Theorem \[thm:Ubound\] is justified. Furthermore, note the equivalent conditions $$\ell_{m}\left(1-\frac{\ell_{m}}{\ell_{n}}\right)
\geq \ell_{m+1}\left(1-\frac{\ell_{m+1}}{\ell_{n}}\right)-\frac{h}{J}
\iff \frac{h}{J} \geq d_{m+1}\left(1-\frac{2\ell_{m}}{\ell_{n}}\right)
-O\left(\frac{d_{m}^{2}}{\ell_{n}}\right),
\label{eq:equivalentconditions}$$ with the last term in disappearing whenever $d_{m+1}
=o\left(\sqrt{\ell_{n}}\right)$. Note that gives us an alternative formulation for $\bar{m}$ in the statement of Theorem \[thm:Ubound\], which we will use to compute $\bar{m}$ below.

Two examples
------------

Two commonly studied degree distributions for the Configuration Model are the Dirac distribution $$q_r(k) = \delta_r(k), \qquad k \in {\mathbb{N}}_0,
\label{eq:Diracdist}$$ for some $r \in {\mathbb{N}}$ (i.e., the $r$-regular graph), and the power-law distribution $$q_{\tau,\delta}(k) = \mathbb{P}\left[d_{i}=\delta+k\right]
= \frac{\left(\delta+k\right)^{-\tau}}{\sum_{i\in{\mathbb{N}}_0}
\left(\delta+i\right)^{-\tau}}, \qquad k \in {\mathbb{N}}_0,
\label{eq:powerlawdist}$$ for some exponent $\tau \in (2,\infty)$ and shift $\delta \in {\mathbb{N}}$.

For these degree distributions we get the following corollary of Theorems \[thm:Ubound\]–\[thm:Lbound\]:

\[cor:mvalues\] (a) For the Dirac-distribution in , $$Jr I_r\left(\tfrac12\right)n -\frac{hn}{2}-o(n) \leq \Gamma_{n}^{\star} \leq \frac{Jr}{4}
n \left(1-\left(\frac{h}{Jr}\right)^2\right)  \pm O\big(n^{3/4}\big).$$ (b) For the power-law distribution distribution in , $\bar{m}$ and $\ell_{\bar{m}}$ are given by and .\
(c) For the power-law distribution distribution in , $\tilde{m}$ is given by .

\(a) Straightforward.\
(b) $\{d_{i}\} _{i=1}^{n}$ are i.i.d. with degree distribution $q_{\tau,\delta}$. Let $s_{\tau,\delta,k} = \sum_{i=1}^{n} \mathbf{1}\left\{d_{i}\leq \delta + k\right\}$, and note that $$\mathbb{E}\left[s_{\tau,\delta,k}\right]
=n\left(1-\frac{\xi_{\tau}\left(\delta+k+1\right)}{\xi_{\tau}\left(\delta\right)}\right)$$ with $\xi_{\tau}\left(a\right)=\sum_{i=a}^{\infty}i^{-\tau}$ for $a\geq0$. We claim that, for $k$ sufficiently small, $s_{\tau,\delta,k}$ is concentrated around its mean. Indeed, define $a_{\delta,k}=\sum_{i}\mathbf{1}\left\{ d_{i}=\delta+k\right\}$, $k\in{\mathbb{N}}_0$, and note that for any i.i.d. sequence we have $a_{\delta,k}\stackrel{d}{=}\mathrm{Bin}\left(n,
p_{\delta,k}\right)$, where $p_{\delta,k}=\mathbb{P}\left[d_{i}=\delta+k\right]$. From Hoeffding’s inequality we get that $$\mathbb{P}\left[\left|a_{\delta,k}-np_{\delta,k}\right|>n^{\frac{1}{2}+\frac{1}{6}}\right]
\leq\exp\left(-2n^{\frac{1}{3}}\right).$$ Hence, for any $k=O(n^{1/6})$, $$\begin{aligned}
\mathbb{P}\left[\left|s_{\tau,\delta,k}-\mathbb{E}
\left[s_{\tau,\delta,k}\right]\right|>n^{\frac{1}{2}+\frac{1}{3}}\right]
&\leq \mathbb{P}\left[\bigcup_{m=0}^{k}
\left|a_{\delta,m}-np_{\delta,m}\right|>n^{\frac{1}{2}+\frac{1}{6}}\right]
\leq n^{\frac{1}{6}}\exp\left(-2n^{\frac{1}{3}}\right).
\label{eq:bnd-s}
\end{aligned}$$ Note that if $p_{\delta,k}=q_{\tau,\delta}(k)$, then $\mathbb{E}[a_{\delta,k}]
=n\,\frac{(\delta+k)^{-\tau}}{\xi_{\tau}(\delta)}$, and w.h.p. $\ell_{n}=n
\frac{\xi_{\tau-1}(\delta)}{\xi_{\tau}(\delta)}+o(n)$. Hence we define $$\kappa = \min\left\{k\in{\mathbb{N}}\colon\,\frac{h}{J}\geq\left(\delta+k-1\right)
\left(1-\left(\frac{\xi_{\tau-1}\left(\delta+k\right)}
{\xi_{\tau-1}\left(\delta\right)}\right)\right)\right\} -1,
\label{eq:defkappa}$$ which certainly satisfies $\kappa= o\left(n^{1/6}\right)$. From (\[eq:equivalentconditions\]) and the monotonicity of (\[eq:functiong\]) it follows that w.h.p. $$\begin{aligned}
\bar{m}
&=n\Bigg[\left(1-\frac{\xi_{\tau}\left(\delta+\kappa\right)}{\xi_{\tau}\left(\delta\right)}\right)\\
&+\min\left\{ y\in\left[0,1\right]\colon\,\frac{h}{J}\geq\left(\delta+\kappa\right)
\left(1-\left(\frac{\xi_{\tau-1}\left(\delta+\kappa\right)}{\xi_{\tau-1}\left(\delta\right)}
+\frac{y\kappa\xi_{\tau}\left(\delta\right)}{\xi_{\tau-1}
\left(\delta\right)}\right)\right)\right\} \Bigg]+o\left(n\right)
\label{eq:mprimeval}
\end{aligned}$$ and $$\frac{\ell_{\bar{m}}}{\ell_{n}}
=\left(\frac{\xi_{\tau-1}\left(\delta+\kappa\right)}{\xi_{\tau-1}\left(\delta\right)}
+\frac{y\kappa\xi_{\tau}\left(\delta\right)}{\xi_{\tau-1}\left(\delta\right)}\right)
+o\left(1\right),
\label{eq:lm/ln}$$ where $y$ is the taken as the argument of the minimum in (\[eq:mprimeval\]). Since we know $\ell_{n}$ up to $o(n)$, this also gives the value of $\ell_{\bar{m}}$.\
(c) Note that $\tilde{m} = \sum_{i=0}^{\kappa} a_{\delta,i}$ where $\kappa$ is the least integer such that $$\delta a_{\delta,0} + (\delta + 1)a_{\delta,0} + \ldots
+ (\delta + \kappa)a_{\delta,\kappa} \geq \tfrac12\ell_n.$$ By the concentration results given above, we see that w.h.p. $$\kappa = \min\left\lbrace m\in{\mathbb{N}}\colon\,
\frac{\xi_{\tau -1}(\delta) +\xi_{\tau -1}(\delta + m+1) }{\xi_{\tau}(\delta)}
\geq \tfrac12 d_{\mathrm{ave}} \right\rbrace$$ and $$\tilde{m} = \frac{n}{\xi_{\tau}(\delta)} \sum_{i=0}^{\kappa} (\delta + i)^{\tau} \: + o(n).
\label{eq:tildem}$$

Proof of Theorem \[thm:Ubound\]
-------------------------------

Consider a sequence of matchings $\left\{\xi_{1},\xi_{2},\ldots,\xi_{M/2}\right\}$ constructed in a dynamical way as outlined above, where $M$ is some even integer. Let $0\leq x\leq M$ be even, and define $z_{x,0}=x$ and $z_{x,t}=\sum_{i=1}^{x}
\sum_{m=1}^{x}\mathbf{1}\left\{\left(i,m\right)\in\xi_{x/2+t}\right\}$. Then $$z_{x,t+1}=z_{x,t}-2\mathbf{1}\left\{ Y_{t+1}\right\},
\label{eq:ziplus1}$$ where $Y_{t}$ is the event that $x+2t-1$ and $x+2t$ are both paired with terms in $\left[x\right]$. Note that $$\mathbb{P}\left[Y_{t+1}\left|\mathscr{G}{}_{x+t}\right.\right]=\frac{z_{x,t}}{x+2+1},
\label{eq:Ytplus1}$$ where $\mathscr{G}_{x+t}$ is the $\sigma$-algebra generated by $\left\{\xi_{1},\ldots,
\xi_{x/2+t}\right\}$. Therefore $$\mathbb{E}\left[z_{x,t+1}\left|\mathscr{G}{}_{x+t}\right.\right]
=  z_{x,t}-\frac{2z_{x,t}}{x+2t+1}
= z_{x,t}\left(\frac{x+2t-1}{x+2t+1}\right)$$ and so $$\mathbb{E}\left[z_{x,t+1}\right]
= z_{0}\prod_{j=0}^{t}\left(\frac{x+2j-1}{x+2j+1}\right)
= x\left(\frac{x-1}{x+2t+1}\right).
\label{eq:Expztplus1}$$ To compute the second moment, observe that $$z_{x,t+1}^{2}=z_{x,t}^{2}-4z_{x,t}\mathbf{1}\left\{ Y_{t+1}\right\}
+4\mathbf{1}\left\{ Y_{t+1}\right\},
\label{eq:zmoment2}$$ and so $$\mathbb{E}\left[z_{x,t+1}^{2}\left|\mathscr{G}{}_{x+t}\right.\right]
= z_{x,t}^{2}-\frac{4z_{x,t}^{2}}{x+2t+1}+\frac{4z_{x,t}}{x+2t+1}
= z_{x,t}^{2}\left(\frac{x+2t-3}{x+2t+1}\right)+\frac{4z_{x,t}}{x+2t+1}.$$ Then $$\begin{aligned}
&\mathbb{E}\left[z_{x,t+1}^{2}\right]\\
& = \mathbb{E}\left[z_{x,t}^{2}\right]\left(\frac{x+2t-3}{x+2t+1}\right)
+\frac{4\mathbb{E}\left[z_{x,t}\right]}{x+2t+1}\\
&= x^{2}\prod_{i=0}^{t}\left(\frac{x+2i-3}{x+2i+1}\right)+\sum_{i=0}^{t}
\frac{4\mathbb{E}\left[z_{x,i}\right]}{x+2i+1}
\prod_{j=i+1}^{t}\left(\frac{x+2j-3}{x+2j+1}\right)\\
&= \frac{x^{2}\left(x-3\right)\left(x-1\right)}{\left(x+2t+1\right)\left(x+2t-1\right)}
+\sum_{i=0}^{t}\frac{4x\left(x-1\right)}{\left(x+2i+1\right)\left(x+2i-1\right)}
\frac{\left(x+2i-1\right)\left(x+2i+1\right)}{\left(x+2t+1\right)\left(x+2t-1\right)} \\
&= \frac{x^{2}\left(x-3\right)\left(x-1\right)}{\left(x+2t+1\right)\left(x+2t-1\right)}
+\frac{4x\left(x-1\right)\left(t+1\right)}{\left(x+2t+1\right)\left(x+2t-1\right)} \\
&= \frac{x\left(x-1\right)}{\left(x+2t+1\right)\left(x+2t-1\right)}\left(x\left(x-3\right)
+4\left(t+1\right)\right),
\label{eq:expzmoment2}
\end{aligned}$$ while $$\left(\mathbb{E}\left[z_{x,t+1}\right]\right)^{2}=x^{2}\left(\frac{x-1}{x+2t+1}\right)^{2}$$ and so $$\mathbb{E}\left[z_{x,t+1}^{2}\right]-\left(\mathbb{E}\left[z_{x,t+1}\right]\right)^{2}
=\frac{x\left(x-1\right)}{x+2t+1}\left(\frac{x\left(x-3\right)
+4\left(t+1\right)}{x+2t-1}-\frac{x\left(x-1\right)}{x+2t+1}\right).$$ It follows that if we let $w_{x,t}=\frac{z_{x,t}}{x+2t}$, $t\geq1$, then $$\begin{aligned}
&\mathbb{E}\left[w_{x,t+1}^{2}\right]-\left(\mathbb{E}\left[w_{x,t+1}\right]\right)^{2}\\
& =  \frac{\frac{x}{x+2\left(t+1\right)}\frac{\left(x-1\right)}{x+2\left(t+1\right)}}
{x+2t+1}\left(\frac{4\left(t+1\right)}{x+2t-1}+\frac{x-3}{1+2\frac{t}{x}-\frac{1}{x}}
-\frac{x-1}{1+2\frac{t}{x}+\frac{1}{x}}\right)\\
&= \frac{\frac{x}{x+2\left(t+1\right)}\frac{\left(x-1\right)}{x+2\left(t+1\right)}}
{x+2t+1}\left(\frac{4\left(t+1\right)}{x+2t-1}+\frac{-4\frac{t}{x}
-4\frac{1}{x}}{\left(1+2\frac{t}{x}-\frac{1}{x}\right)\left(1+2\frac{t}{x}
+\frac{1}{x}\right)}\right)\\
&= \frac{4\frac{x}{x+2\left(t+1\right)}\frac{\left(x-1\right)}{x+2\left(t+1\right)}}
{x+2t+1}\frac{t+1}{x+2t-1}\left(1-\frac{1}{1+2\frac{t}{x}+\frac{1}{x}}\right).
\label{eq:wvar}
\end{aligned}$$

Observe also that for $$\bar{z}_{x,t} = \sum_{i=1}^{x}\sum_{m=x+1}^{M}
\mathbf{1}\left\{ \left(i,m\right)\in\xi_{x/2+t}\right\} =x-z_{x,t}
\label{eq:zbar}$$ and $$\bar{w}_{x,t} = \frac{\bar{z}_{x,t}}{x+2t}=\frac{x}{x+2t}-w_{x,t}$$ the same variance calculations follow, so that $\mathbb{E}\left[\bar{w}_{x,t+1}^{2}\right]
-\left(\mathbb{E}\left[\bar{w}_{x,t+1}\right]\right)^{2}$ is also given by (\[eq:wvar\]). For $\alpha\in\left(0,1\right)$ and $1\leq i\leq k\left(\alpha\right)$ with $k\left(\alpha\right)
=M/\left\lfloor M^{\alpha}\right\rfloor $, let $x_{i}=i\left\lfloor M^{\alpha}\right\rfloor $ and note that $$\begin{aligned}
&\sum_{i=1}^{k\left(\alpha\right)} \left(\mathbb{E}\left[\bar{w}_{x,t+1}^{2}\right]
-\left(\mathbb{E}\left[\bar{w}_{x,t+1}\right]\right)^{2}\right)\\
&=\frac{1}{2}M^{-2}\left(M-1\right)^{-1}\left(M-3\right)^{-1}\sum_{i=1}^{k\left(\alpha\right)}
x_{i}\left(x_{i}-1\right)\left(M-x_{i}\right)\left(1-\frac{x_{i}}{M-1}\right)
=O\left(M^{-\alpha}\right).
\label{eq:2ndmomentbndforpath}
\end{aligned}$$ From Markov’s inequality we have that $$\begin{aligned}
&\mathbb{P}\left[\exists\,i\mbox{ such that }\frac{\left|\bar{z}_{x_{i},\left(M-x_{i}\right)/2}
-\mathbb{E}\left[\bar{z}_{x_{i},\left(M-x_{i}\right)/2}\right]\right|}{M}
>M^{-\frac{\alpha}{3}}\right]\\
&= \mathbb{P}\left[\exists\, i\mbox{ such that }\frac{\left|\bar{z}_{x_{i},\left(M-x_{i}\right)/2}
-\mathbb{E}\left[\bar{z}_{x_{i},\left(M-x_{i}\right)/2}\right]\right|^{2}}{M^{2}}
>M^{-\frac{2\alpha}{3}}\right]\\
&= \mathbb{P}\left[\exists\, i\mbox{ such that } \left|\bar{w}_{x_{i},\left(M-x_{i}\right)/2}
-\mathbb{E}\left[\bar{w}_{x_{i},\left(M-x_{i}\right)/2}\right]\right|^{2}
>M^{-2\alpha/3}\right]= O\left(M^{-\alpha/3}\right)
\end{aligned}$$ and thus we have that w.h.p. for every $1\leq i\leq k\left(\alpha\right)$, $$\left|\bar{z}_{x_{i},\left(M-x_{i}\right)/2}-\mathbb{E}\left[\bar{z}_{x_{i},
\left(M-x_{i}\right)/2}\right]\right|=O\left(M^{1-\alpha/3}\right).
\label{eq:bndziconcentration}$$ Now suppose that $x_{i}\leq x\leq x_{i+1}$. Then, clearly, $\bar{z}_{x_{i},
\left(M-x_{i}\right)/2}-M^{\alpha}\leq\bar{z}_{x,\left(M-x\right)/2}\leq
\bar{z}_{x_{i},\left(M-x_{i}\right)/2}+M^{\alpha}$, and via (\[eq:Expztplus1\]) and (\[eq:zbar\]) we conclude that w.h.p. for every $1\leq x\leq M$ we have $$\label{eq:boundzbarvariance}
\begin{aligned}
&\left|\bar{z}_{x,\left(M-x\right)/2}-\mathbb{E}\left[\bar{z}_{x,\left(M-x\right)/2}\right]\right|\\
& \leq\left|\bar{z}_{x,\left(M-x\right)/2}-\bar{z}_{x_{i},\left(M-x_{i}\right)/2}\right|
+\left|\bar{z}_{x_{i},\left(M-x_{i}\right)/2}
-\mathbb{E}\left[\bar{z}_{x_{i},\left(M-x_{i}\right)/2}\right]\right|\\
&\qquad +\left|\mathbb{E}\left[\bar{z}_{x_{i},\left(M-x_{i}\right)/2}\right]
-\mathbb{E}\left[\bar{z}_{x,\left(M-x\right)/2}\right]\right|\\
& =\left|\bar{z}_{x,\left(M-x\right)/2}-\bar{z}_{x_{i},\left(M-x_{i}\right)/2}\right|
+\left|\bar{z}_{x_{i},\left(M-x_{i}\right)/2}-x_{i}\left(\frac{M-x_{i}}{M-1}\right)\right|\\
&\qquad +\left|x_{i}\left(\frac{M-x_{i}}{M-1}\right)-x\left(\frac{M-x}{M-1}\right)\right|\\
&\leq M^{\alpha}+O\left(M^{1-\alpha/3}\right)+M^{\alpha}.
\end{aligned}$$ Now let $\gamma_{s}$ be any configuration on the path $\gamma:\boxminus\rightarrow\boxplus$ defined above. Then w.h.p. $$\begin{aligned}
\mathcal{H}\left(\gamma_{s}\right)-\mathcal{H}\left(\boxminus\right)
&= J\left|E\left(\gamma_{s},\overline{\gamma_{s}}\right)\right|-hs\\
&= J\bar{z}_{\ell_{\gamma_{s}},\left(\ell_{n}-\ell_{\gamma_{s}}\right)/2}-hs
=J\ell_{\gamma_{s}}\left(1-\frac{\ell_{\gamma_{s}}}{\ell_{n}}\right)-hs+O\left(\ell_{n}^{3/4}\right),
\end{aligned}$$ where the last line follows from with $x=\ell_{m}$, $M=\ell_{n}$ and $\alpha=\frac{3}{4}$, and uses the fact that $\mathbb{E}\left[\bar{z}_{x,t}\right]
=x\left(1-\frac{x-1}{x+2t+1}\right)$. By definition, this quantity is maximised when $\ell_{\gamma_{s}}$ is replaced by $\ell_{\bar{m}}$, from which the statement of the theorem follows.

Proof of Theorem \[thm:Lbound\]
-------------------------------

Setting $x=\tfrac12$ in , we get that the probability of there being any configuration of total degree $\ell_n/2$ having a boundary size $y\ell_n$ is bounded from above by $$\exp\left[\ell_{n}\log\left(\tfrac12\eta\left(\tfrac12\right)
\left(\tfrac12-y\right)^{-\left(\tfrac12-y\right)}y^{-y}\right)\right].
\label{eq:expbound}$$ By the law of large numbers, w.h.p. we have that $n=\ell_{n}/d_{\mathrm{ave}}+
o\left(n\right)$. Combining this with $\left|\left\{ U\subseteq V\colon\,\ell_U
=\ell_{n}x\right\} \right|\leq2^n$ we get that $\eta\left(\tfrac12\right) \leq 2^{1/d_{\mathrm{ave}}}$. It follows that if $y< I_{d_{\mathrm{ave}}}\left(\tfrac12\right)$, then (\[eq:expbound\]) decays exponentially. Hence, all configurations $\sigma$ with $\ell_\sigma=\ell_n/2$ have, w.h.p., an energy at least $${\mathcal{H}}(\sigma) \geq J I_{d_{\mathrm{ave}}}\left(\tfrac12\right) \ell_n - h |\sigma| + {\mathcal{H}}(\boxminus),$$ and the lower bound on $\Gamma^\star_n$ in  follows.

Tail properties of the dynamically constructed ${\mathrm{CM}}_n$ {#tailprop}
================================================================

In this section we explore some properties of the dynamical construction of ${\mathrm{CM}}_n$ introduced in Section \[CMdynamic\].

Trivial tail $\sigma$-algebra
-----------------------------

Let $V_{n}=\left(v_{1},\ldots,v_{n}\right)$ be the vertices with corresponding degree sequence $$\vec{d}_{n}=\left(d_{1},\ldots,d_{n}\right),$$ and let $G_{n}=\left(V_{n},E_{n}\right)$ and $G_{n}\prime=\left(V_{n},E_{n}\prime
\right)$ be two independent Configuration Models with the same degree sequence $\vec{d}_{n}$. We will extend $G_{n}$ and $G_{n}\prime$ to larger graphs, $G_{n+t}
=\left(V_{n+t},E_{n+t}\right)$ and $G_{n+t}\prime=\left(V_{n+t},E_{n+t}\prime\right)$, respectively, with degree sequence $$\vec{d}_{n}=\left(d_{1},\ldots,d_{n},d_{n+1},\ldots d_{n+t}\right),$$ by utilising a pairing scheme similar to the one introduced in Section \[CMdynamic\]:

-   If $\xi_{m}$ is a uniform random matching of the integers $\left\{ 1,\ldots,2m\right\}$, denoted by $\xi_{m}=\left\{ \left(x_{1},x_{2}\right),\ldots,\left(x_{2m-1},x_{2m}\right)
    \right\} $, then take $u_{1}$ to be uniform on $\left\{ 1,\ldots,2m\right\} $ and $u_{2}$ to be uniform on $\left\{ 1,\ldots,2m,2m+1\right\} $. If $u_{2}=2m+1$, then set $\xi_{m+1}=\xi_{m}\cup\left\{ \left(2m+1,2m+2\right)\right\} $. Otherwise add to $\xi_{m}$ the pairs $\left(2m+1,u_{1}\right)$ and $\left(2m+2,u_{2}\right)$ when $u_{1}\neq u_{2}$, and when $u_{1}=u_{2}$, only add to $\xi_{m}$ the pair $\left(2m+2,u_{2}\right)$. In either case, if there are two remaining terms that are unpaired, then pair them to each other and add this pair to $\xi_{m}$. Needless to say, we also remove from $\xi_{m}$ old pairs that were undone by the introduction of $2m+1$ and $2m+2$. Again, this construction leads to $\xi_{m+1}$, a uniform matching of the points $\left\{1,\ldots,2m+2\right\}$.

Now construct the coupled graphs $\left(G_{n+t},G_{n+t}\prime\right)$ by starting with $\left(G_{n},G_{n}\prime\right)$ and using the same uniform choice $$\left\{u_{i}\right\} _{i=1}^{|\vec{d}_{n+t}|-|\vec{d}_{n}|}$$ to determine new edges in both graphs. Note that, under this scheme, every term (half-edge) $s>|\vec{d}_{n}|$ is paired with the same term in $G_{n+t}$ as in $G_{n+t}\prime$. In other words, for all $1\leq j\leq|\vec{d}_{n+t}|$ we have $\left(s,j\right)\in E_{n+t}$ if and only if $\left(s,j\right)\in E_{n+t}\prime$. For $s\leq|\vec{d}_{n}|$ and $1\leq j\leq|\vec{d}_{n+t}|$, we have $$\begin{aligned}
&\mathbb{P}\left[\mathbf{1}_{\left\{ \left(s,j\right)\in E_{n+t}\right\} }
\neq \mathbf{1}_{\left\{ \left(s,j\right)\in E_{n+t}\prime\right\} }\right]\\
&\leq  \mathbb{P}\left[\bigcap_{i=1}^{|\vec{d}_{n+t}|
-|\vec{d}_{n}|}\left\{ u_{i}\neq s\right\} \right]
= \prod_{i=|\vec{d}_{n}|}^{|\vec{d}_{n+t}|}\left(1-\frac{1}{i-1}\right)
=\frac{|\vec{d}_{n}|-2}{|\vec{d}_{n+t}|-1}.
\end{aligned}$$ Hence $$\mathbb{P}\left[\bigcup_{s=1}^{\left|\vec{d}_{n}\right|}
\left\{ \mathbf{1}_{\left\{ \left(s,j\right)\in E_{n+t}\right\} }
\neq \mathbf{1}_{\left\{ \left(s,j\right)\in E_{n+t}\prime\right\} }\right\} \right]
\leq\frac{|\vec{d}_{n}|(|\vec{d}_{n}|-2)}
{|\vec{d}_{n+t}|-1}.$$ Thus, we conclude that $\mathbb{P}\left[G_{n+t}\neq G_{n+t}\prime\right] =
O\left(\frac{1}{t}\right)$.

We can now make the following standard argument to show that the process above has a trivial tail-sigma-algebra. Let $\mathscr{F}_{t}=\sigma\left(\xi_{1},
\ldots.\xi_{t}\right)$ and $\mathscr{F}_{t}^{+}=\sigma\left(\xi_{t+1},\ldots\right)$. The tail sigma-algebra is given by $\mathscr{T}=\cap_{n\in\mathbb{N}}
\mathscr{F}_{t}^{+}$. For any $A\in\mathscr{T}$, there is a sequence of events $A_{1},A_{2},\ldots$ such that $$\lim_{t\to\infty}\mathbb{P}\left[A_{t}\triangle A\right]=0,$$ and hence also $$\lim_{t\to\infty}\mathbb{P}\left[A_{t}\cap A\right] =\mathbb{P}\left[A\right],
\qquad \lim_{t\to\infty}\mathbb{P}\left[A_{t}\right]=\mathbb{P}\left[A\right].$$ But, since $A\in\mathscr{F}_{t}^{+}$ for all $t$, it follows that $\mathbb{P}\left[A_{t}
\cap A\right]=\mathbb{P}\left[A_{t}\right]\mathbb{P}\left[A\right]$, and hence $\mathbb{P}\left[A\right]=\mathbb{P}\left[A\right]^{2}$. This shows that $\mathscr{T}$ is a trivial sigma-algebra. Therefore, given $\left\{ d_{i}\right\} _{i\in{\mathbb{N}}}$ (but also by the law of large numbers for i.i.d. sequences), $$\limsup_{n\to\infty}\frac{\Gamma_{n}^{\star}}{n}= \gamma^*_+,
\qquad \liminf_{n\to\infty}\frac{\Gamma_{n}^{\star}}{n}= \gamma^*_-,$$ for some $\gamma^*_+,\gamma^*_- \in{\mathbb{R}}$ with $\gamma^*_+ \geq \gamma^*_-$.

Oscillation bounds
------------------

It is possible to obtain bounds on the possible oscillations of $n\mapsto
\Gamma_{n}^{\star}/n$.

\[lem: gammadifference\] Let $G=(V,E)$ and $\tilde{G}=(\tilde{V},\tilde{E})$ be two connected graphs. Suppose that $\left|E\nabla\tilde{E}\right|\leq k$ under some labelling of the vertices in $V$ and $\tilde{V}$ (i.e., a one-to-one map from $V$ to $\tilde{V}$). Then $$|\Gamma^{\star}-\tilde{\Gamma}^{\star}| \leq Jk+h\big| |\tilde{V}|-|V| \big|.$$

W.l.o.g. assume that $|\tilde{V}|\geq|V\|$. Given the labelling of the vertices that satisfies the above condition, let $\gamma\colon\,\boxminus\to\boxplus$, denoted by $\gamma=\left(\gamma_{1},\ldots,\gamma_{m}\right)$, be an optimal path for the Glauber dynamics on $G$. Now let $\tilde{\gamma}\colon\,
\tilde{\boxminus}\to\tilde{\boxplus}$ be the Glauber path of configurations on $\tilde{G}$, denoted by $\tilde{\gamma}=(\tilde{\gamma}_{1},\ldots,\tilde{\gamma}_{m},
\tilde{\gamma}_{m+1},\ldots,\tilde{\gamma}_{m+|\tilde{V}|-|V|})$, and defined by the following rule: whichever vertex $v\in V$ is flipped at step $i$ in the path $\gamma$, flip the corresponding vertex $\tilde{v}\in\tilde{V}$ also at step $i$ in $\tilde{\gamma}$. For steps $m+1,\ldots,m+|\tilde{V}|-|V|$, flip the remaining $-1$ valued vertices in any arbitrary order. Then it follows that, for $1\leq i\leq m$, $$\tilde{\mathcal{H}}\left(\tilde{\gamma}_{i}\right)
-\tilde{\mathcal{H}}\left(\tilde{\boxminus}\right)
=J|\tilde{E}\left(\tilde{\gamma}_{i},\overline{\tilde{\gamma}_{i}}\right)|
-h\left|\tilde{\gamma}_{i}\right|
\leq J\left(|E\left(\gamma_{i},\overline{\gamma_{i}}\right)|+k\right)
-h\left|\tilde{\gamma}_{i}\right|.$$ Similarly, for $m\leq i\leq m+|\tilde{V}|-|V|$, we have $$\tilde{\mathcal{H}}\left(\tilde{\gamma}_{i}\right)
-\tilde{\mathcal{H}}\left(\tilde{\boxminus}\right)
\leq Jk-h\left(\left|\gamma_{i}\right|-\left|\boxplus\right|\right).$$ It follows that $\tilde{\Gamma}^{\star}\leq\Gamma^{\star}+Jk-h(|\tilde{V}|-|V|)$. A similar argument gives $\Gamma^{\star}\leq\tilde{\Gamma}^{\star}+Jk
+h||\tilde{V}|-|V||$.

Now let $G=\left(V,E\right)$ and $\tilde{G}=(\tilde{V},\tilde{E})$ be two Configuration Models and suppose w.l.o.g. that the total degree of the vertices in $V$ is $\ell_{V}$ and the total degree of vertices in $\tilde{V}$ is $\ell_{\tilde{V}}\geq\ell_{V}$. Let $G_{t}$ and $\tilde{G}_{t}$ be the extension of each these two graphs, obtained by adding vertices $\left\{ v_{1},\ldots,v_{t}\right\} $ and $\left\{ \tilde{v}_{1},\ldots,\tilde{v}_{t}\right\}$, both with the same degree sequence $\left\{d_{1},\ldots,d_{t}\right\}$. We will couple the construction leading to the two graphs $G_{t}$ and $\tilde{G}_{t}$ in the following manner: for $1\leq i\leq\sum_{k=1}^{t}d_{k}$, choose $u_{i}$ uniformly as described above, and pair $i$ with $u_{i}$ in $G_{t}$. Let $\delta_{i}=\left(\ell_{\tilde{V}}-\ell_{V}\right)/\left[\left(\ell_{\tilde{V}}
+i-1\right)\left(\ell_{V}+i-1\right)\right]$ and set $\tilde{u}_{i}=u_{i}$ with probability $1-\delta_{i}$, and with probability $\delta_{i}$ independently and uniformly pick one of the remaining $\left(\ell_{\tilde{V}}-\ell_{V}\right)$ points. Then $$\mathbb{E}[|E_{t}\nabla\tilde{E_{t}}|]
\leq |E\nabla\tilde{E}|+\sum_{i}\delta_{i} \leq |E\nabla\tilde{E}|
+2\left(\ell_{\tilde{V}}-\ell_{V}\right).$$ Hence, from Markov’s inequality and from Lemma \[lem: gammadifference\], it follows that, w.h.p. and for any function $f(t)$ such that $\lim_{t\to\infty}
f(t)=\infty$, $$\left|\tilde{\Gamma^{\star}}_{t}-\Gamma^{\star}_{t}\right|
\leq J\left(|E\nabla\tilde{E}|+2(\ell_{\tilde{V}}-\ell_{V})+f(t)\right)
-h\left(\big||\tilde{V}|-|V|\big|\right).$$ Hence, by this pairing scheme, we have that $\tilde{\Gamma^{\star}_{t}}/\Gamma^{\star}_{t}
\to 1$ as $t\to \infty$.

Appendix A {#appendix-a .unnumbered}
==========

Note that any configuration $\sigma$ chosen uniformly from all configurations of size $|\sigma|$ satisfies ($\mathbb{E}$ denotes expectation w.r.t. bond percolation) $$\mathbb{E}\left(\left|E\left(\sigma,\overline{\sigma}\right)\right|\right)
= \mu_{\left|\sigma\right|} \quad \mbox{ with } \quad
\mu_{\left|\sigma\right|} = p\left|\sigma\right|\left(n-\left|\sigma\right|\right).$$ Using Chernoff’s inequality and a union bound, we can show that if $|\sigma|=\Theta(n)$, then $$\mathcal{H}\left(\sigma\right)-\mathcal{H}\left(\boxminus\right)
= J\mu_{\left|\sigma\right|}[1\pm o(1)]-h\left|\sigma\right|.$$ Furthermore, any $\sigma$ of size $|\sigma|\leq[1-o(1)]\frac{n}{2}$ has (modulo small fluctuations) a downhill path to $\boxminus$ (e.g. by flipping $+1$ spins in any arbitrary order), while every $|\sigma|\geq[1+o(1)]\frac{n}{2}$ has a downhill path to $\boxplus$ (e.g. by flipping $-1$ spins in any arbitrary order). This proves hypothesis (H), and the claim in .

[99]{}

G. Ben Arous and R. Cerf, Metastability of the three-dimensional Ising model on a torus at very low temperature, Electron. J. Probab. 1, paper 10, 1996.

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability and small eigenvalues in Markov chains, J. Phys. A 33, L447–L451, 2000.

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability in stochastic dynamics of disordered mean-field models, Probab. Theory Relat. Fields 119, 99–161, 2001.

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability and low lying spectra in reversible Markov chains, Comm. Math. Phys. 228, 219–255, 2002.

A. Bovier, M. Eckhoff, V. Gayrard and M. Klein, Metastability in reversible diffusion processes. I. Sharp asymptotics for capacities and exit times, J. Eur. Math. Soc. 6, 399–424, 2004.

A. Bovier and F. den Hollander, *Metastability – A Potential-Theoretic Approach*, Grundlehren der mathematischen Wissenschaften 351, Springer, 2015.

A. Bovier, F. den Hollander and C. Spitoni, Homogeneous nucleation for Glauber and Kawasaki dynamics in large volumes and low temperature, Ann. Probab. 38, 661–713, 2010.

A. Bovier and F. Manzo, Metastability in Glauber dynamics in the low temperature limit: beyond exponential asymptotics, J. Stat. Phys. 107, 757–779, 2002.

M. Cassandro, A. Galves, E. Olivieri and M.E. Vares, Metastable behavior of stochastic dynamics: A pathwise approach, J. Stat. Phys. 35, 603–634, 1984.

O. Catoni and R. Cerf, The exit path of a Markov chain with rare transitions, ESAIM Probab. Statist. 1, 95–144, 1997.

E.N.M. Cirillo and F.R. Nardi, Relaxation height in energy landscapes: an application to multiple metastable states, J. Stat. Phys. 150, 1080–1114, 2013.

E.N.M. Cirillo, F.R. Nardi and J. Sohier, Metastability for general dynamics with rare transitions: escape time and critical configurations, J. Stat. Phys. 161, 365–403, 2015.

E.N.M. Cirillo and E. Olivieri, Metastability and nucleation for the Blume-Capel model: different mechanisms of transition, J. Stat. Phys. 83, 473–554, 1996.

A. Dembo and A. Montanari, Ising models on locally tree-like graphs, Ann. Appl. Probab. 20, 565–592, 2010.

S. Dommers, Metastability of the Ising model on random regular graphs at zero temperature, to appear in Probab. Theory Relat. Fields, DOI: 10.1007/s00440-015-0682-0, 2015.

S. Dommers, C. Giardinà and R. van der Hofstad, Ising models on power-law random graphs, J. Stat. Phys. 141, 638–660, 2010.

R. van der Hofstad, *Random Graphs and Complex Networks, Volume I*, to appear with Cambridge University Press. (File can be downloaded from <http://www.win.tue.nl/~rhofstad/>.)

O. Jovanovski, Metastability for the Ising Model on the hypercube, \[arXiv:1508.07769\], 2015.

R. Kotecký and E. Olivieri, Stochastic models for nucleation and crystal growth, Probabilistic Methods in Mathematical Physics (Siena 1991), riverside NY: World Scientific 264–275, 1992.

R. Kotecký and E. Olivieri, Droplet Dynamics for asymmetric Ising model, J. Stat. Phys. 70, 1121–1148, 1993.

R. Kotecký and E. Olivieri, Shapes of growing droplets - a model of escape from the metastable phase, J. Stat. Phys. 75, 409–506, 1994.

F. Manzo, F.R. Nardi, E. Olivieri and E. Scoppola, On the essential features of metastability: tunnelling time and critical configurations, J. Stat. Phys. 115, 591–642, 2004.

E. Mossel and A. Sly, Exact thresholds for Ising-Gibbs samplers on general graphs, Ann. Appl. Probab. 41, 294–328, 2013.

F.R. Nardi and E. Olivieri, Low temperature stochastic dynamics for an Ising model with alternating field, Markov Proc. Relat.  Fields. 2, 117–166, 1996.

E.J. Neves and R.H. Schonmann, Critical droplets and metastability for a Glauber dynamics at very low temperature, Comm. Math. Phys. 137, 209–230, 1991.

E.J. Neves and R.H. Schonmann, Behavior of droplets for a class of Glauber dynamics at very low temperature, Probab. Theory Relat. Fields. 91, 331–354, 1992.

E. Olivieri and E. Scoppola, Markov chains with exponentially small transition probabilities: First exit problem from general domain I. The reversible case, J. Stat. Phys. 79, 613–647, 1995.

E. Olivieri and E. Scoppola, Markov chains with exponentially small transition probabilities: First exit problem from general domain II. The general case, J. Stat. Phys. 84, 987–1041, 1996.

E. Olivieri and M.E. Vares, *Large Deviations and Metastability*, Encyclopedia of Mathematics and its Applications 100, Cambridge University Press, Cambridge, 2005.

[^1]: The research in this paper was supported by NWO Gravitation Grant 024.002.003-NETWORKS. The work of SD was supported also by DFG Research Training Group 2131.
