# A triangle process on graphs
with given degree sequence

Colin Cooper
Department of Informatics
King’s College
London WC2B 4BG, U.K.
<EMAIL_ADDRESS>
Martin Dyer
School of Computing
University of Leeds
Leeds LS2 9JT, U.K.
<EMAIL_ADDRESS>
Research supported by EPSRC grant EP/S016562/1,“Sampling in hereditary
classes”. Catherine Greenhill
School of Mathematics and Statistics
UNSW Sydney
NSW 2052, Australia
<EMAIL_ADDRESS>Research supported an Australian Research Council
grant DP190100977.

(January 20 2023)

###### Abstract

The triangle switch Markov chain is designed to generate random graphs with
given degree sequence, but having more triangles than would appear under the
uniform distribution. Transition probabilities of the chain depends on a
parameter, called the activity, which is used to assign higher stationary
probability to graphs with more triangles. In previous work we proved
ergodicity of the triangle switch chain for regular graphs. Here we prove
ergodicity for all sequences with minimum degree at least 3, and show rapid
mixing of the chain when the activity and the maximum degree are not too
large. As far as we are aware, this is the first rigorous analysis of a Markov
chain algorithm for generating graphs from a a known non-uniform distribution.

##  1 Introduction

Randomly generating graphs has been the subject of considerable research
interest. See, for example, [1, 2, 3, 7, 11, 14, 17, 19, 36, 39, 40, 52]. A
comprehensive survey of work to date is given in [25].

Generation using Markov chains has been an important approach in this area,
particularly Markov chains based on switches, for example [3, 11, 14, 17, 36,
38, 39, 40, 52]. Switches delete a pair of edges from the graph and insert a
pair using the same four vertices. They have the important property that they
preserve the degree sequence of the graph. Thus they are useful for generating
regular graphs, or other graphs with a given degree sequence. Markov chains
also give a dynamic reconfigurability property, which is useful in some
applications, for example [11, 17, 40].

For any such Markov chain, three questions arise. Firstly, can the chain
generate any graph in the chosen class? In other words, is the Markov chain
ergodic? Secondly, if so what is its equilibrium distribution? Thirdly, what
is the rate of convergence to equilibrium? That is, what is the mixing time of
the chain?

We investigate the _triangle switch Markov chain_ , which we abbreviate as
“$\triangle$-switch chain”. The $\triangle$-switch chain was introduced in
[12] to generate regular random graphs with more triangles than would appear
under the uniform distribution. See section 1.2 below for the relevant
definitions. The chain was proved to be ergodic for 3-regular graphs, and a
variant was shown to produce $\Omega(n)$ triangles in $O(n)$ steps of the
chain. The proof of ergodicity involved finding a sequence of transitions of
the chain ($\triangle$-switches) which transform any 3-regular graph into
disjoint copies of $K_{4}$ together with a disjoint 6-vertex graph, and then
showing that any such graph can be transformed into another using
$\triangle$-switches. This proof is not well suited to standard methods for
proving rapid mixing of the chain. A further obstacle is that some of the
variants studied in [12] do not seem to be time-reversible, a requirement for
most approaches to proving rapid mixing.

The proof of ergodicity in [12] was extended in [13] to $d$-regular graphs,
for any $d$. The proof involved finding a sequence of $\triangle$-switches
which transform any $d$-regular graph into disjoint copies of $K_{d+1}$
together with a disjoint graph, called a “fragment”, with at most $2d$
vertices; then showing that any such graph can be transformed into another
using $\triangle$-switches. This required a different approach to proving
ergodicity of the fragments, by showing that any step of the flip chain of
[40] can be simulated by at most three $\triangle$-switches.

In this paper we extend and generalise the result of [12] by showing that any
step of the switch chain [11] can be simulated by at most five
$\triangle$-switches. Moreover this holds for all graphs with a given degree
sequence such that the minimum degree is at least 3. We prove this in section
2.

Moreover, the simulation approach allows us to prove rapid mixing for some
degree sequences of the variant of the chain described in section 1.2. This
chain has an equilibrium distribution in which the probability of a graph is
exponentially weighted by its number of triangles. The analysis is given in
section 4. Such distributions on graphs seem relevant for researchers
modelling real-world networks, such as social networks, which contain many
triangles [23, 35].

We state our results more formally in section 1.3. As far as we are aware,
this is the first rigorous analysis of a Markov chain algorithm for generating
graphs from a a known non-uniform distribution.

###  1.1 Notation and definitions

Let $[n]$ denote the set $\\{1,2,\ldots,n\\}$ and let $G=(V,E)$ be an
$n$-vertex (simple) graph with vertex set $V=[n]$. The degree sequence
$\boldsymbol{d}=(d_{1},d_{2},\ldots,d_{n})$ of $G$ is given by $d_{i}=\deg(i)$
for all $i\in[n]$. An arbitrary sequence $\boldsymbol{d}$ of $n$ nonnegative
integers is called _graphical_ if there is any graph which has degree sequence
$\boldsymbol{d}$. Given the sequence, this property can be tested efficiently
and constructively using, for example, the Havel-Hakimi algorithm [28, 31].

We assume without loss of generality that $d_{1}\geq d_{2}\geq\cdots\geq
d_{n}$, so $d_{1}$ is the maximum degree and $d_{n}$ the minimum degree. We
note that $d_{1},d_{n}$ are usually denoted by $\Delta,\delta$, but we will
not do so here. If $d_{1}=d_{n}=d$, the $d$-regular case, $d$ is common degree
of all vertices. Define

$M=M(\boldsymbol{d})=\sum_{i=1}^{n}d_{i}=2|E|=n\bar{d},\qquad
M_{2}=M_{2}(\boldsymbol{d})=\sum_{i=1}^{n}d_{i}(d_{i}-1),$

where $\bar{d}$ is the _average_ degree. We will denote the number of
triangles in $G$ by

$t(G)=\big{|}\big{\\{}\\{i,j,k\\}\subseteq V:ij,jk,ki\in E\big{\\}}\big{|}.$

If $G$ has degree sequence $\boldsymbol{d}$ then the maximum value for $t(G)$
is $\nicefrac{{1}}{{3}}\sum_{i=1}^{n}\binom{d_{i}}{2}=M_{2}/6$. (The sum is
over all ways of choosing two edges of the triangle meeting a given vertex,
the divisor $\nicefrac{{1}}{{3}}$ because this counts each triangle three
times.) In the regular case, this maximum is achieved by a $d$-regular graph
consisting of the disjoint union of $n/(d+1)$ cliques of size $(d+1)$.

We will make the assumption that $M_{2}\geq M$, since this is implicit in some
of the proofs of asymptotic distributions below. Now let
$\mathcal{G}_{n,\boldsymbol{d}}$ be the set of all labelled graphs with degree
sequence $\boldsymbol{d}$. The _switch chain_ is a Markov chain which walks on
$\mathcal{G}_{n,\boldsymbol{d}}$ by choosing two non-incident edges uniformly
at random, and randomising these two edges without changing the degree
sequence. Here we consider a restricted switch chain, in which a switch is
only allowed if it changes the set of triangles in the graph. This is achieved
by $\triangle$-switches. A $\triangle^{+}$-switch is designed to increase the
number of triangles, and a $\triangle^{-}$-switch to decrease this number. See
Fig. 1, where $a_{2}a_{1}va_{3}a_{4}$ is a path in $G$ such that $a_{1}a_{3}$
and $a_{2}a_{4}$ are non-edges, which is transformed to a triangle
$va_{1}a_{3}$ and a vertex-disjoint edge $a_{2}a_{4}$ and vice versa.

$v$$a_{1}$$a_{3}$$a_{2}$$a_{4}$$\triangle^{+}$-switch$\triangle^{-}$-switch$v$$a_{1}$$a_{3}$$a_{2}$$a_{4}$

Fig. 1: : The $\triangle$-switches

We show in Lemma 3.2 below that the $\mathbb{E}[t(G)]$ for a uniformly chosen
random graph $G\in\mathcal{G}_{n,\boldsymbol{d}}$ is
$\mu(\boldsymbol{d})=M_{2}^{3}/M^{3}$ asymptotically if $d_{1}=o(\sqrt{M})$.
Our chain will have a non-uniform stationary distribution, where graph $G$ has
probability proportional to $\lambda^{t(G)}$, for some parameter
$\lambda=\lambda(n)\geq 1$, which we call the _activity_. When $\lambda>1$ the
$\triangle$-switch chain will generate graphs with more triangles than
expected in a uniform random graph with the same degree sequence. In fact, we
will show that $\mathbb{E}[t(G)]\sim\lambda\mu$ in this distribution, if
$\lambda$ and $d_{1}$ are small enough.

We denote the transitions in the triangle process as $\triangle$-switches. We
may use $\triangle^{+}$-switch to denote a switch which is known to create a
triangle, and $\triangle^{-}$-switch for a switch which is known to break a
triangle. However, a given $\triangle$-switch can simultaneously create one or
more triangles and break one or more triangles, in which case it can be viewed
as either a $\triangle^{+}$-switch or a $\triangle^{-}$-switch. We reserve the
term “switch”, without qualification, for the transitions of the switch chain,
as studied in [11], for example.

###  1.2 Markov chain

Recall that $t(G)$ denote the number of triangles in the graph
$G\in\mathcal{G}_{n,\boldsymbol{d}}$. Suppose the current state of the chain
is $G\in\mathcal{G}_{n,\boldsymbol{d}}$. The transition procedure of the
$\triangle$-switch chain, with parameter $\lambda\geq 1$, is shown in Fig. 2.

At the current state $G\in\mathcal{G}_{n,\boldsymbol{d}}$ do choose a pair of
non-adjacent edges $F=\\{a_{1}a_{2},\,a_{3}a_{4}\\}$ uniformly at random
choose a perfect matching $F^{\prime}$ of $\\{a_{1},a_{2},a_{3},a_{4}\\}$
uniformly at random let $H:=([n],E^{\prime})$ where
$E^{\prime}:=\big{(}E(G)\setminus F\big{)}\cup F^{\prime}$ if
$F^{\prime}\cap\big{(}E(G)\setminus F\big{)}=\emptyset$ and XXXXXX
$\big{(}N(a)\cap
N(a^{\prime})\big{)}\setminus\\{a_{1},a_{2},a_{3},a_{4}\\}\neq\emptyset$ for
some $aa^{\prime}\in F\cup F^{\prime}$ then the next state is $H$ with
probability $\min\\{1,\lambda^{t(H)-t(G)}\\}$ otherwise stay at $G$ end if end

Fig. 2: The transition procedure of the $\triangle$-switch chain with
parameter $\lambda$ on $\mathcal{G}_{n,\boldsymbol{d}}$

Comparing the transition procedure in Fig. 2 with Fig. 1, taking
$aa^{\prime}=a_{1}a_{3}$ satisfies the condition $\big{(}N(a)\cap
N(a^{\prime})\big{)}\setminus\\{a_{1},a_{2},a_{3},a_{4}\\}\neq\emptyset$.

At every step we have $P_{\lambda}(G,G)\geq 1/3$ and hence the
$\triangle$-switch chain is aperiodic. We prove in section 2 below that the
chain is irreducible, and hence ergodic, provided the minimum degree
$d_{n}\geq 3$.

Define the probability distribution $\pi$ by
$\pi(G)=\lambda^{t(G)}/Z_{\lambda}(\boldsymbol{d})$ for all
$G\in\mathcal{G}_{n,\boldsymbol{d}}$, where

$Z_{\lambda}(\boldsymbol{d})=\sum_{H\in\mathcal{G}_{n,\boldsymbol{d}}}\lambda^{t(H)}$

is the normalising factor. Let $a(\boldsymbol{d})$ be the number of unordered
pairs of non-incident distinct edges in any element of
$\mathcal{G}_{n,\boldsymbol{d}}$, given by

$a(\boldsymbol{d})=\binom{M/2}{2}-\frac{M_{2}}{2}.$ (1)

If $P_{\lambda}(G,H)>0$ and $G\neq H$ then, assuming without loss of
generality that $t(H)\leq t(G)$, we have

$\pi(G)\,P_{\lambda}(G,H)=\frac{\lambda^{t(G)}}{Z_{\lambda}(\boldsymbol{d})}\,\frac{1}{3a(\boldsymbol{d})}\,\lambda^{t(H)-t(G)}=\frac{\lambda^{t(H)}}{Z_{\lambda}(\boldsymbol{d})}\,\frac{1}{3a(\boldsymbol{d})}=\pi(H)\,P_{\lambda}(H,G).$

Hence the chain satisfies the detailed balance equations with respect to
$\pi$, so $\pi$ is the unique stationary distribution of the chain, which is
of Metropolis-Hastings type [30].

For technical reasons, we will use a modified $\triangle$-switch chain,
obtained by replacing $t(H)$ by $\min\\{t(H),\nu\\}$ and replacing $t(G)$ by
$\min\\{t(G),\nu\\}$ in the transition procedure Figure 2, where $\nu(n)=\log
n/\log\log n$. By the same argument as above, the modified $\triangle$-switch
chain has stationary distribution which assigns to graph $G$ a probability
proportional to $\lambda^{\min\\{t(G),\nu\\}}$. The modified
$\triangle$-switch chain is polynomial-time indistinguishable from the
$\triangle$-switch chain when $\lambda$ and $\mu$ are small enough. See
section 4.2.

###  1.3 Our results

In section 3 we will show that $t(G)$ is approximately
$\textrm{Pois}(\lambda\mu)$ in the equilibrium distribution $\pi$ of the
$\triangle$-switch chain if $\lambda$ and $\mu$ are small enough. In section 4
we will show that the chain is rapidly mixing for smaller values of $\lambda$
and $\mu$.

However, we must first show that the $\triangle$-switch chain is irreducible
on $\mathcal{G}_{n,\boldsymbol{d}}$. This was proved for regular graphs in
[13], by showing that (a) every $d$-regular graph could be transformed by a
sequence of $\triangle$-switches into the disjoint union of $\lfloor
n/(d+1)\rfloor$ copies of $K_{d+1}$ and one other small component, called a
“fragment”, and (b) using $\triangle$-switches, it is possible to specify the
vertices in each copy of $K_{d+1}$ and to transform fragments into other
fragments. This approach is not suitable for proving rapid mixing of the
$\triangle$-switch chain by existing methods. Here we will use the “two-stage
direct canonical path construction” method from [14] to prove rapid mixing,
and this informs our approach to proving irreducibility.

It is known that all graphs with a given degree sequence are connected by
switches [38, 51]. In other words, the switch chain is irreducible on
$\mathcal{G}_{n,\boldsymbol{d}}$ for all $n$ and $\boldsymbol{d}$.

Hence in order to prove that the $\triangle$-switch chain is irreducible on
$\mathcal{G}_{n,\boldsymbol{d}}$, it suffices to show that every switch
$(G,H)$ can be simulated using a sequence of $\triangle$-switches. To do this
we will specify a sequence

$\sigma_{GH}:\quad G=X_{0},X_{1},\ldots,X_{\kappa}=H$

such that $(X_{i},X_{i+1})$ is a $\triangle$-switch for $i=0,\ldots,\kappa-1$.
The sequence $\sigma_{GH}$ is called a _simulation path_ for $(G,H)$ of length
$\kappa$. Rather than simply prove existence of such a path, we will specify
one uniquely for each possible switch $(G,H)$, and show that all our
simulation paths have length at most 5. We will do this for degree sequences
with minimum degree at least 3, proving the following.

######  Theorem 1.1.

Let $\boldsymbol{d}$ be a graphical degree sequence with $d_{1}\geq
d_{2}\cdots\geq d_{n}\geq 3$ and let $\lambda\geq 1$ be a constant. Then the
$\triangle$-switch chain with parameter $\lambda$ is irreducible on
$\mathcal{G}_{n,\boldsymbol{d}}$.

Note that this is not true in general if $d_{n}<3$, see [13]. The above result
can be viewed as a _reconfiguration_ result on
$\mathcal{G}_{n,\boldsymbol{d}}$, generalising that given in [13].
Reconfiguration problems have been a topic of much recent interest in graph
theory. See Nishimura [44] for an introduction.

Our second result gives a condition under which we can deduce rapid mixing of
the modified $\triangle$-switch chain with parameter $\lambda$ from rapid
mixing of the switch chain.

######  Theorem 1.2.

Let $\mathcal{D}$ be a family of graphical degree sequences such that for all
$\boldsymbol{d}\in\mathcal{D}$ of length $n$ we have $d_{1}\geq
d_{2}\geq\cdots\geq d_{n}\geq 3$. Let $\lambda=\lambda(n)\geq 1$ be a function
of $n$. Suppose that there exists an $\alpha\in(0,1)$ such that
$\lambda\mu(\boldsymbol{d})\leq\log^{\alpha}n$ for every
$\boldsymbol{d}\in\mathcal{D}$ of length $n$ and all large enough $n$. If the
switch chain is rapidly mixing on $\mathcal{G}_{n,\boldsymbol{d}}$ for all
$\boldsymbol{d}\in\mathcal{D}$ then the same is true for the modified
$\triangle$-switch chain with parameter $\lambda$.

The switch chain is known to be rapidly mixing for large classes of graphical
sequences, in particular regular sequences [11, 24] and all graphical
sequences from P-stable families [16, 20]. By Theorem 1.2, the
$\triangle$-switch chain is also rapidly mixing for these graphical sequences,
whenever $\lambda$ and $\boldsymbol{d}$ satisfy the conditions of the theorem.

To conclude this section we give some background on the use of canonical paths
for bounding the mixing time of Markov chains, and the two-stage direct
canonical path construction method which we will use to prove Theorem 1.2.
Then in section 2 we prove Theorem 1.1, and in section 4 we prove Theorem 1.2.

###  1.4 Background on canonical paths and mixing time

For further details, see for example Jerrum [33] or Sinclair [48].

Let $\mathcal{M}$ be an ergodic Markov chain with finite state space $\Omega$,
transition matrix $P$ and stationary distribution $\pi$. Let
$\mathcal{G}=(\Omega,E(\mathcal{M}))$ be the graph underlying $\mathcal{M}$,
so the edge set of $\mathcal{G}$ corresponds to (non-loop) transitions of
$\mathcal{M}$.

Given two probability distributions $\sigma$, $\rho$ on $\Omega$, the _total
variation distance_ between them, denoted
$\mathrm{d}_{\mathrm{TV}}(\sigma,\rho)$, is defined by

$\mathrm{d}_{\mathrm{TV}}(\sigma,\rho)=\tfrac{1}{2}\sum_{x\in\Omega}|\sigma(x)-\rho(x)|=\max_{A\subseteq\Omega}\,(\sigma(A)-\rho(A)).$
(2)

The _mixing time_ $\tau(\varepsilon)$ of $\mathcal{M}$ is given by

$\tau(\varepsilon)=\max_{x\in\Omega}\,\min\,\\{t\geq 0\ |\
\mathrm{d}_{\mathrm{TV}}(P^{t}_{x},\pi)\leq\varepsilon\\},$

where $P^{t}_{x}$ is the distribution of the random state $X_{t}$ of the
Markov chain after $t$ steps with initial state $x$.

Let the eigenvalues of $P$ be

$1=\mu_{0}>\mu_{1}\geq\mu_{2}\cdots\geq\mu_{N-1}>-1$

and define $\mu_{\ast}=\max\\{\mu_{1},\,|\mu_{N-1}|\\}$. Then, see for example
[48, Proposition 1], the mixing time of $\mathcal{M}$ satisfies

$\tau(\varepsilon)\leq(1-\mu_{\ast})^{-1}\left(\ln(1/\pi^{\ast})+\ln(\varepsilon^{-1})\right)$
(3)

where $\pi^{\ast}=\min_{x\in\Omega}\pi(x)$ is the smallest stationary
probability. In applications we often focus on the second-largest eigenvalue
$\mu_{1}$, if necessary by making the Markov chain lazy (replacing the
transition matrix $P$ by $(I+P)/2$ to ensure that all eigenvalues are
nonnegative).

Jerrum and Sinclair [34] introduced the _canonical path_ method for bounding
$\mu_{1}$. For each pair $x,y\in\Omega$, we choose a path $\gamma_{xy}$ from
$x$ to $y$ in the graph $\mathcal{G}$ underlying the Markov chain. A
_canonical_ choice of paths seeks to produce a small value of the critical
parameter $\bar{\rho}(\Gamma)$, the _congestion_ of the set of paths
$\Gamma=\\{\gamma_{xy}\mid x,y\in\Omega\\}$, defined by

$\bar{\rho}(\Gamma)=\max_{e\in
E(\mathcal{M})}Q(e)^{-1}\sum_{\begin{subarray}{c}x,y\in\Omega\\\
e\in\gamma_{xy}\end{subarray}}\,\pi(x)\pi(y)|\gamma_{xy}|$

where $Q(e)=\pi(u)\,P(u,v)$ when $e=uv\in E(\mathcal{M})$. Then

$(1-\mu_{1})^{-1}\leq\bar{\rho}(\Gamma),$ (4)

so a low congestion can lead to a good bound on the mixing time, using (3).
See [48, Theorem 5] or [33].

In [14], the _two-stage direct canonical path construction method_ was
described. Here we have two ergodic Markov chains $\mathcal{M}$ and
$\mathcal{M}^{\prime}$, with state spaces $\Omega$ and $\Omega^{\prime}$,
respectively. We assume that we have a set of canonical paths for
$\mathcal{M}^{\prime}$, and that we can simulate each transition $(Y,Z)$ of
$\mathcal{M}^{\prime}$ by a sequence $\sigma_{YZ}$ of transitions of
$\mathcal{M}$:

$\sigma_{YZ}:\quad Y=X_{0},X_{1},\ldots,X_{\kappa}=Z$

such that $(X_{i},X_{i+1})$ is a transition of $\mathcal{M}$. We call
$\sigma_{YZ}$ a $(\mathcal{M},\mathcal{M}^{\prime})$-_simulation path_ and let
$\Sigma=\\{\sigma_{YZ}\mid(Y,Z)\in E(\mathcal{M}^{\prime})\\}$ be the set of
all $(\mathcal{M},\mathcal{M}^{\prime})$-simulation paths.

For each transition $e\in E(\mathcal{M})$, let

$\Sigma(e)=\\{\sigma\in\Sigma\mid e\in\sigma\\}$

be the set of all simulations paths which use the transition $e$. We define
the parameters

$\ell(\Sigma)=\max_{\sigma\in\Sigma}|\sigma|,\quad B(\Sigma)=\max_{e\in
E(\mathcal{M})}|\Sigma(e)|$ (5)

representing the maximum length of any simulation path and the maximum number
of simulation paths through a given transition of $\mathcal{M}$, respectively.
Finally, the _simulation gap_ between the two chains is defined by

$D(\mathcal{M},\mathcal{M}^{\prime})=\max_{\begin{subarray}{c}uv\in
E(\mathcal{M})\\\ zw\in
E(\mathcal{M}^{\prime})\end{subarray}}\frac{\pi^{\prime}(z)P^{\prime}(z,w)}{\pi(u)P(u,v)}$
(6)

and the _stationary ratio_ is defined by

$R(\mathcal{M},\mathcal{M}^{\prime})=\max_{x,y\in\Omega}\frac{\pi(x)\,\pi(y)}{\pi^{\prime}(x)\pi^{\prime}(y)}=\left(\max_{x\in\Omega}\frac{\pi(x)}{\pi^{\prime}(x)}\right)^{2}.$
(7)

Note that $\pi$ and $\pi^{\prime}$ are both positive on their domains as
$\mathcal{M}$, $\mathcal{M}^{\prime}$ are ergodic and reversible.

The following is a slight simplification of [14, Theorem 2.1], tailored to the
case that $\Omega=\Omega^{\prime}$. (If $\Omega=\Omega^{\prime}$ then the
surjection $h$ mentioned in [14, Theorem 2.1] can be taken to be the
identity.) We will also take the opportunity to correct a minor error in [14,
Theorem 2.1], where the factor $R(\mathcal{M},\mathcal{M}^{\prime})$ was
omitted.

######  Theorem 1.3.

Let $\mathcal{M}$ and $\mathcal{M}^{\prime}$ be two ergodic Markov chains on a
set $\Omega$. Let $\Gamma^{\prime}$ be a set of canonical paths in
$\mathcal{M}^{\prime}$ and let $\Sigma$ be a set of
$(\mathcal{M},\mathcal{M}^{\prime})$-simulation paths. Then there exists a set
of canonical paths in $\mathcal{M}$ whose congestion satisfies

$\bar{\rho}(\Gamma)\leq
D(\mathcal{M},\mathcal{M}^{\prime})\,R(\mathcal{M},\mathcal{M}^{\prime})\,\ell(\Sigma)\,B(\Sigma)\,\bar{\rho}(\Gamma^{\prime}).$

###### Proof.

In the proof of [14, Theorem 2.1] it is shown that

$\bar{\rho}(\Gamma)\leq
D(\mathcal{M},\mathcal{M}^{\prime})\,\ell(\Sigma)\,\max_{uv\in
E(\mathcal{M})}\,\sum_{\begin{subarray}{c}zw\in E(\mathcal{M}^{\prime})\\\
\sigma_{zw}\in\Sigma(uv)\end{subarray}}\frac{1}{\pi^{\prime}(z)P^{\prime}(z,w)}\sum_{\begin{subarray}{c}x,y\in\Omega^{\prime}\\\
zw\in\gamma^{\prime}_{xy}\end{subarray}}\pi(x)\pi(y)\,|\gamma^{\prime}_{xy}|$

and that

$\max_{uv\in E(\mathcal{M})}\,\sum_{\begin{subarray}{c}zw\in
E(\mathcal{M}^{\prime})\\\
\sigma_{zw}\in\Sigma(uv)\end{subarray}}\frac{1}{\pi^{\prime}(z)P^{\prime}(z,w)}\sum_{\begin{subarray}{c}x,y\in\Omega^{\prime}\\\
zw\in\gamma^{\prime}_{xy}\end{subarray}}\pi^{\prime}(x)\pi^{\prime}(y)\,|\gamma^{\prime}_{xy}|\leq
B(\Sigma)\,\bar{\rho}(\Gamma^{\prime}).$

The result follows as $\pi(x)\pi(y)\leq
R(\mathcal{M},\mathcal{M}^{\prime})\,\pi^{\prime}(x)\pi^{\prime}(y)$. ∎

We remark that in the analysis of the flip chain given in [14], the above
theorem is applied twice. In one application the missing factor $R$ is exactly
1, and in the other application it can be bounded above by a constant close to
1 (say 2). So the stated bound on the mixing time of the flip chain in [14] is
too small by a factor of at most 2, which is of no consequence. However, in
the highly non-uniform distribution on triangles below, the ratio
$R(\mathcal{M},\mathcal{M}^{\prime})$ becomes rather more significant.

##  2 Irreducibility

To prove Theorem 1.1, we will show that any switch can be simulated by a
sequence of at most five $\triangle$-switches. We will present the
constructions diagrammatically, with the following conventions: solid lines
represent known edges of $G$, dotted lines represent known non-edges, and
dashed lines represent non-edges involved in the current $\triangle$-switch.

Suppose that a $\triangle$-switch $(G,H)$ replaces the edges $a_{1}a_{2}$,
$a_{3}a_{4}$ with the edges $a_{1}a_{3}$, $a_{2}a_{4}$. We classify switches
into three types, depending on whether one or both of the _diagonals_
$a_{1}a_{4}$, $a_{2}a_{3}$ is present or absent, as shown in Fig. 3. Note that
the diagonals have the form $a_{j}a_{5-j}$ for $j=1,2$.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$Type (a)$a_{1}$$a_{2}$$a_{3}$$a_{4}$Type
(b)$a_{1}$$a_{2}$$a_{3}$$a_{4}$Type (c) Fig. 3: The three types of switch,
depending on how many diagonals are present

Let $D=\\{a_{1},a_{2},a_{3},a_{4}\\}$ be the vertices of the switch, and
$A_{i}=N(a_{i})\setminus D$ ($i\in[4]$) be the neighbours of $a_{i}$ outside
of $D$. Note that $|A_{i}|=\deg(a_{i})-\deg_{D}(a_{i})$, so $|A_{i}|\geq
d_{n}-1$ or $|A_{i}|\geq d_{n}-2$. Thus, since $d_{n}\geq 3$, we have
$A_{i}\neq\emptyset$ for all $i\in[4]$ in any switch.

######  Lemma 2.1.

Suppose that $(G,H)$ is a switch which removes the edges $a_{1}a_{2}$,
$a_{3}a_{4}$ and replaces them with the edges $a_{1}a_{3}$, $a_{2}a_{4}$.
Further suppose that at least one of the following holds:

  * _(i)_

The switch is Type  _(b)_ or Type  _(c)_. That is, at least one diagonal is
present.

  * _(ii)_

The switch is Type  _(a)_ , and some pair of distinct elements of
$D=\\{a_{1},a_{2},a_{3},a_{4}\\}$ have a common neighbour in $[n]\setminus D$.

  * _(iii)_

There is a triangle on vertices $a_{j},u,w$ for some vertices $u,w$ which
satisfy $u\not\in A_{5-j}$ and $\\{u,w\\}\cap D=\emptyset$, where $j\in[4]$.

Then there is a $\triangle$-switch simulation path of length at most 4 which
simulates the switch $(G,H)$.

###### Proof.

For future reference, we will number the cases which arise when defining the
simulation paths. This will be needed later in the proof of rapid mixing. We
treat these cases in order, so we only move to (II) if (I) does not hold, and
so on.

  * (I)

If the switch $(G,H)$ is itself a $\triangle$-switch then the simulation path
is $G,H$ which has length 1. This occurs if and only if at least one of
$A_{1}\cap A_{2}$, $A_{1}\cap A_{3}$, $A_{3}\cap A_{4}$, $A_{2}\cap A_{4}$ is
nonempty.

  * (II)

Now suppose that the switch has Type (a) (both diagonals absent) and
$(A_{1}\cap A_{4})\cup(A_{2}\cap A_{3})$ is non-empty. After relabelling if
necessary, assume that $A_{1}\cap A_{4}\neq\emptyset$. Then there is a
simulation path of length 2, shown below.

$v$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$\triangle^{+}$$\longrightarrow$$v$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$\triangle^{-}$$\longrightarrow$$v$$a_{1}$$a_{2}$$a_{3}$$a_{4}$

  * (III)

Next, suppose that the switch has Type (b) (both diagonals present) and
$(A_{1}\cap A_{4})\cup(A_{2}\cap A_{3})$ is non-empty. After relabelling if
necessary, $A_{1}\cap A_{4}\neq\emptyset$. Again, there is a simulation path
of length 2, as shown below.

$v$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$\triangle^{-}$$\longrightarrow$$v$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$\triangle^{+}$$\longrightarrow$$v$$a_{1}$$a_{2}$$a_{3}$$a_{4}$

  * (IV)

Note that if none of (I), (II) or (III) hold then $A_{i}\cap A_{j}=\emptyset$
for all distinct $i,j\in[4]$. Next we suppose that, after relabelling if
necessary,

    * –

at least one of the diagonal edges $a_{j}a_{5-j}$ is present, and the
symmetric difference $A_{i}\oplus A_{5-i}$ is nonempty, where
$\\{i,j\\}=\\{1,2\\}$, or

    * –

there is a triangle on vertices $a_{j},u,w$ for two distinct vertices
$u,w\in[n]\setminus D$. (Here we do not care how many diagonal edges are
present.)

In the first subcase, choose $(i,u)$ to be lexicographically-least. Then after
relabelling if necessary, we can assume that $u$ is the lexicographically-
least element of $A_{1}\setminus A_{4}$. In the second subcase, choose
$(j,u,w)$ to be the lexicographically-least triple satisfying the
requirements. Then after relabelling if necessary, we can assume that $j=1$.
In both cases, we have a simulation path of length 2, consisting of first
replacing edges $a_{1}u,a_{3}a_{4}$ by $a_{1}a_{3},ua_{4}$ and then replacing
edges $ua_{4},a_{1}a_{3}$ by edges $a_{1}u,a_{2}a_{4}$. Under the given
conditions, each of these operations is a $\triangle$-switch, as required. We
illustrate the simulation path below for the first subcase when exactly one
diagonal $a_{2}a_{3}$ is present (noting that it this still gives a sequence
of two $\triangle$-switches if $a_{1}a_{4}$ is also present), and in the
second subcase when neither diagonal is present (noting that this still gives
a sequence of two $\triangle$-switches if one or both diagonals are present).

$u$$a_{1}$
$\,a_{2}$$\,a_{3}$$\,a_{4}$$\triangle^{+}$$\longrightarrow$$u$$a_{1}$
$\,a_{2}$$\,a_{3}$$\,a_{4}$$\triangle^{-}$$\longrightarrow$$u$$a_{1}$
$\,a_{2}$$\,a_{3}$$\,a_{4}$

$w$ $u$$a_{1}$ $\,a_{2}$$\,a_{3}$$\,a_{4}$$\triangle^{-}$$\longrightarrow$$w$
$u$$a_{1}$ $\,a_{2}$$\,a_{3}$$\,a_{4}$$\triangle^{+}$$\longrightarrow$$w$
$u$$a_{1}$ $\,a_{2}$$\,a_{3}$$\,a_{4}$

  * (V)

Next, suppose that the switch has Type (c), so exactly one diagonal
$a_{j}a_{5-j}$ is present, and that $A_{i}=A_{5-i}$, and that $G[A_{i}]$ has
at least one edge, where $\\{i,j\\}=\\{1,2\\}$. By relabelling if necessary,
we may assume that diagonal $a_{1}a_{4}$ is present, and for ease of notation
let $A=A_{2}=A_{3}$. Let $(u,v)$ be the lexicographically-least pair of
vertices in $A$ such that $uv$ is an edge of $G$. Then $a_{2},u,v$ and
$a_{3},u,v$ both determine triangles, while $u\not\in A_{1}$ and $v\not\in
A_{4}$ as we are not in (I). Then there is a simulation path of length 4 as
shown below.

$v$$a_{2}$ $a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{-}$$\longrightarrow$$v$$a_{2}$
$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{+}$$\longrightarrow$$v$$a_{2}$
$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{-}$$\longrightarrow$$v$$a_{2}$
$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{+}$$\longrightarrow$$v$$a_{2}$
$a_{1}$$a_{4}$$a_{3}$$u$

  * (VI)

Finally, suppose that the switch has Type (c), so exactly one diagonal
$a_{j}a_{5-j}$ is present, and that $A_{i}=A_{5-i}$, and that $G[A_{i}]$ has
no edges, where $\\{i,j\\}=\\{1,2\\}$, Again, by relabelling if necessary, we
assume that diagonal $a_{1}a_{4}$ is present, and write $A=A_{2}=A_{3}$. Note
that $|A|\geq 2$ as $d_{D}(a_{2})=d_{D}(a_{3})=1$. Let $(u,v)$ be the
lexicographically-least pair of distinct elements in $A$, and let $w$ be the
smallest-labelled vertex in $N(v)\setminus D$, which exists as the minimum
degree is at least 3. Then $w\not\in A=A_{3}$ as $v\in A$ and $vw\in E$. We
can construct the following simulation path of length 4.

$w$$v$$a_{2}$$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{+}$$\longrightarrow$$w$$v$$a_{2}$$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{+}$$\longrightarrow$$w$$v$$a_{2}$$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{-}$$\longrightarrow$$w$$v$$a_{2}$$a_{1}$$a_{4}$$a_{3}$$u$$\triangle^{-}$$\longrightarrow$$w$$v$$a_{2}$$a_{1}$$a_{4}$$a_{3}$$u$

To complete the proof, observe that (I), (III) and (IV) together cover all
Type (b) switches, while Type (c) switches are covered by combining (I), (IV),
(V) and (VI). This proves the lemma under assumption (i). The proof for
assumption (ii) is covered by (I) and (II) together, while (IV) completes the
proof for assumption (iii). ∎

For the remainder of the proof we assume that the assumptions of Lemma 1 do
not hold. Hence the switch has Type (a), that is, no diagonals are present.
Furthermore, no two vertices in $D$ have a common neighbour outside $D$, and
there is no triangle of the form $a_{j}uw$ with $\\{u,w\\}\cap D=\emptyset$,
where $j\in[4]$.

In this situation it is possible that the switch edges $a_{1}a_{2}$,
$a_{3}a_{4}$ lie in different components of $G$, so that $H$ has one fewer
components that $G$. Only a $\triangle^{-}$-switch can reduce the number of
components, and so our strategy is to “plant” a triangle of the form
$a_{j},u,w$ with $u,w\not\in D$ distinct. By assumption, $ua_{5-j}$ is not an
edge as $A_{j}\cap A_{5-j}=\emptyset$. Hence, after planting the triangle, we
can simulate the switch using the simulation path described in part (IV) of
Lemma 2.1, then “unplant” the planted triangle. There is one exceptional
situation where we will not plant a triangle, but instead will simulate the
switch $(G,H)$ with a simulation path of length three. (This is case (IXa) of
Lemma 2.3 below.)

We will make use of the following lemma to plant a triangle on some element of
$D$. This lemma will be applied to graphs in $\mathcal{G}_{n,\boldsymbol{d}}$,
or to graphs in $\mathcal{G}_{n,\boldsymbol{d}}$ with one edge removed.

######  Lemma 2.2.

Let $G$ be a graph on the vertex set $[n]$. Suppose $v\in[n]$ has a set of
three distinct neighbours $R=\\{r_{1},r_{2},r_{3}\\}$, with $\deg(r_{i})\geq
2$ for $i=1,2,3$. Assume that there is no triangle in $G$ which contains $v$
and an element of $R$.

  1. _(i)_

Then there is a $\triangle^{+}$-switch $(G,\widetilde{G})$ such that
$\widetilde{G}$ contains a triangle $T$ with $v\in T$ and $R\cap
T\neq\emptyset$.

  2. _(ii)_

Furthermore, we can insist that $r_{1}\in T$ unless for $j=2,3$ there is a
5-cycle which contains the path $r_{1}vr_{j}$, but no 4-cycle in $G$ contains
this path.

###### Proof.

Let $\ell$ be the length of the shortest cycle in $G$ which contains a path of
the form $r_{i}vr_{j}$, where $r_{i},r_{j}$ are distinct elements of $R$. If
no such cycle exists, set $\ell=\infty$. By assumption, $\ell\geq 4$. First
suppose that $\ell=4$. After relabelling the vertices in $R$ if necessary,
assume that the cycle contains the path $r_{1}vr_{2}$ together with some
vertex $w$. (For definiteness, let $w$ be the least-labelled common neighbour
of $r_{1}$ and $r_{2}$.) Note that $vw$ and $r_{2}r_{3}$ are not edges of $G$,
by assumption. Then we can plant a triangle on $v,r_{1},w$ as follows:

$v$$r_{1}\,$$\,r_{2}$$\,r_{3}$$w$$\triangle^{+}$$\longrightarrow$$v$$r_{1}\,$$\,r_{2}$$\,r_{3}$$w$

Next suppose that $\ell=5$. After relabelling elements of $R$ if necessary, we
can assume that the 5-cycle is $vr_{1}w_{1}w_{2}r_{2}v$, where
$w_{1},w_{2}\not\in\\{v\\}\cup R$ are distinct. For definiteness, choose
$(w_{1},w_{2})$ to be lexicographically least among all possibilities. Note
that $vw_{1}$ is a non-edge in $G$ by assumption, and $w_{2}r_{3}$ is a non-
edge in $G$ as $\ell\neq 4$. We can “plant” a triangle as follows:

$v$$r_{1}\,$$\,r_{2}$$\,r_{3}$$\,w_{1}$$\,w_{2}$$\,w_{3}$$\triangle^{+}$$\longrightarrow$$v$$r_{1}\,$$\,r_{2}$$\,r_{3}$$\,w_{1}$$\,w_{2}$$\,w_{3}$

Now suppose that $\ell\geq 6$. After relabelling vertices in $R$ if necessary,
suppose that we have a path $w_{1}r_{1}vr_{2}w_{2}$ in $G$, where
$w_{1},w_{2}\not\in\\{v\\}\cup R$ are distinct. (For definiteness, choose
$(w_{1},w_{2})$ to be lexicographically least among all options.) Note that
$r_{1}r_{2}$ is a non-edge in $G$ by assumption, and $w_{1}w_{2}$ is a non-
edge in $G$ as $\ell\neq 5$. Then we can plant a triangle as follows:

$v$$r_{1}\,$$\,r_{2}$$\,r_{3}$$\,w_{1}$$\,w_{2}$$\,w_{3}$$\triangle^{+}$$\longrightarrow$$v$$r_{1}\,$$\,r_{2}$$\,r_{3}$$\,w_{1}$$\,w_{2}$$\,w_{3}$

In all cases, we have (uniquely) identified a $\triangle^{+}$-switch which
produces a graph $\widetilde{G}$ with the same degree sequence as $G$ which
contains a triangle satisfying the stated conditions. This proves (i).

To prove the second statement, adapt the above proof by letting $\ell$ be the
length of the shortest cycle which contains the path $r_{1}vr_{j}$ for some
$j\in\\{2,3\\}$. If $\ell\neq 5$ then the $\triangle$-switch described above
creates a triangle $T$ with $r_{1}\in T$, as required. If $\ell=5$ then the
$\triangle$-switch described above works if and only if $w_{2}r_{3}$ is not an
edge, assuming (after swapping the labels of $r_{2}$ and $r_{3}$ if necessary)
that the 5-cycle $vr_{1}w_{1}w_{2}r_{2}v$ is present. This completes the proof
of (ii). ∎

To describe how to remove a planted triangle, we need some terminology. Let
$(G,\widetilde{G})$ be a $\triangle$-switch, where $\widetilde{G}$ is obtained
from $G$ by deleting the edges $e_{1},e_{2}$ and inserting the edges
$e_{3},e_{4}$. If $\widetilde{H}$ is any graph which contains the edges
$e_{3},e_{4}$ and does not contain $e_{1},e_{2}$, then the _inverse_ of the
$\triangle$-switch $(G,\widetilde{G})$, applied to $\widetilde{H}$, is the
$\triangle$-switch $(\widetilde{H},H)$ where $H$ is obtained from
$\widetilde{H}$ by deleting the edges $e_{3},e_{4}$ and inserting the edges
$e_{1},e_{2}$. This matches the usual notion of an inverse operation when
$\widetilde{H}=\widetilde{G}$, since then $H=G$, but here we need to apply
inverse $\triangle$-switches when $\widetilde{H}\neq\widetilde{G}$.

For us, $(G,\widetilde{G})$ will be a $\triangle^{+}$-switch which plants a
triangle. Then we will perform two or three $\triangle$-switches from
$\widetilde{G}$ to reach a graph $\widetilde{H}$ which contains $e_{3},e_{4}$
but not $e_{1},e_{2}$. Finally we will remove the planted triangle by applying
the inverse of $(G,\widetilde{G})$ to $\widetilde{H}$. There is one exception,
which is case (IXa) below, where we do not plant a triangle but instead
simulate the required switch with a simulation path of length three.

######  Lemma 2.3.

Suppose that $(G,H)$ is a switch which removes the edges $a_{1}a_{2}$,
$a_{3}a_{4}$ and replaces them with the edges $a_{1}a_{3}$, $a_{2}a_{4}$.
Further suppose that the following conditions all hold:

  * •

The switch has Type  _(a)_ (no diagonals present),

  * •

no pair of vertices in $D=\\{a_{1},a_{2},a_{3},a_{4}\\}$ have a common
neighbour, and

  * •

there is no triangle on vertices $a_{j},u,w$ with $\\{u,w\\}\cap D=\emptyset$,
where $j\in[4]$.

Then there is a $\triangle$-switch simulation path of length at most five
which simulates the switch $(G,H)$.

###### Proof.

We will number the cases which arise when defining the simulation paths. This
will be needed later in the proof of rapid mixing. Since Lemma 2.1 has cases
(I)–(VI), here our numbering starts from (VII). We treat these cases in order,
so we only move to (VIII) if (VII) does not hold, and so on.

  * (VII)

First suppose that after at least one of $a_{1},a_{2},a_{3},a_{4}$ has degree
at least 4. Choose the least-labelled element of $D$ which has degree at least
4: after relabelling the elements of $D$ if necessary, we can assume that
$a_{1}$ has degree at least 4. We apply Lemma 2.2(i) with $v=a_{1}$, and $R$ a
set of three neighbours of $a_{1}$ other than $a_{2}$. This identifies a
$\triangle^{+}$-switch $(G,\widetilde{G})$ where $\widetilde{G}$ contains a
triangle of the form $a_{1},u,w$. From $\widetilde{G}$ we can perform the two
$\triangle$-switches described in Lemma 2.1, part (IV), to delete the edges
$a_{1}a_{2},a_{3}a_{4}$ and replace them with $a_{1}a_{3}$, $a_{1}a_{4}$ using
two $\triangle$-switches. From the resulting graph $\widetilde{H}$ we apply
the inverse of the $\triangle^{+}$-switch $(G,\widetilde{G})$. This “unplants”
the planted triangle and takes us to $H$. This gives a simulation path of
length 4.

  * (VIII)

Next, assume that $\deg(a_{i})=3$ for all $i\in[4]$ and that there is a path
of length at most 2 in $G\setminus D$ between some element of $A_{j}$ and some
element of $A_{2+j}$, for some $j\in\\{1,2\\}$. Take a shortest such path, and
by relabelling if necessary assume that $j=1$. Let $A_{1}=\\{u_{1},u_{2}\\}$
and $A_{3}=\\{v_{1},v_{2}\\}$ and by relabelling these vertices if necessary,
assume that the path has endvertices $u_{1}$, $v_{1}$. Note that $u_{2}\not\in
A_{4}$ and $v_{1}\not\in A_{2}$, since no two elements of $D$ have a common
neighbour (by assumption).

(VIIIa): If the path has length 1 then the edge $u_{1}v_{1}$ is present and we
can plant a triangle as follows.

$a_{1}$$u_{2}\,$$u_{1}$$a_{3}$$v_{2}$$v_{1}$$\triangle^{+}$$\longrightarrow$$a_{1}$$u_{2}\,$$u_{1}$$a_{3}$$v_{2}$$v_{1}$

We have a triangle $a_{1},u_{1},v_{2}$ which allows us to perform the two
$\triangle$-switches as described in Lemma 2.1, part (IV), to simulate the
required switch. From the resulting graph, we apply the inverse of the
triangle-planting $\triangle$-switch, to “unplant” the triangle and produce
$H$. This gives a simulation path of length 4.

(VIIIb): If the path has length 2 then (after possibly relabelling as
described above), $u_{1}$ and $v_{1}$ have a common neighbour $w$, where we
choose $w$ to be the least-labelled common neighbour of $u_{1}$, $v_{1}$. Note
that $a_{3}w\notin E$ because $\deg(a_{3})=3$, and $u_{2}v_{1}\notin E$ since
otherwise it would be an edge between the neighbourhoods of $a_{1},a_{3}$.
Then we can plant a triangle as follows:

$a_{1}$$u_{1}\,$$u_{2}$$a_{3}$$v_{2}$$v_{1}$$w$$\triangle^{+}$$\longrightarrow$$a_{1}$$u_{1}\,$$u_{2}$$a_{3}$$v_{2}$$v_{1}$$w$

Now we have a triangle $a_{1},u_{1},w$ which we can use to perform the two
$\triangle^{+}$-switches as specified in Lemma 2.1, case (IV). From the
resulting graph, we apply the inverse of the triangle-planting
$\triangle$-switch, to “unplant” this triangle and produce $H$. This gives a
simulation path of length 4.

  * (IX)

Here we assume that $\deg(a_{i})=3$ for all $i\in[4]$ and that there is no
path of length at most 2 between an element of $A_{j}$ and an element of
$A_{2+j}$, for $j=1,2$. Let $A_{1}=\\{u_{1},u_{2}\\}$.

(IXa) First suppose that there is an edge between two neighbours of $u_{j}$,
and by relabelling if necessary we can assume that $j=1$. Then $w_{1}w_{2}\in
E$ for some $w_{1},w_{2}\in\mbox{N}(u_{1})$ which are distinct from $a_{1}$.
(For definiteness, let $(w_{1},w_{2})$ be the lexicographically-least such
pair.) In this subcase, we do not plant a triangle: instead we use the
following simulation path of length 3, where $v$ is the least-labelled element
of $A_{3}$. Note that $u_{1}a_{3}\not\in E$ since $A_{1}\cap A_{3}=\emptyset$,
and $vw_{2}\not\in E$ since $u_{1}$ and $v$ are at distance at least 3 in $G$.

$u_{1}\,$$w_{1}\,$$\,w_{2}$$a_{2}\,$$a_{1}\,$$\,a_{4}$$\,a_{3}$$\,v$$\triangle^{-}$$\longrightarrow$$u_{1}\,$$w_{1}\,$$\,w_{2}$$a_{2}\,$$a_{1}\,$$\,a_{4}$$\,a_{3}$$\,v$$\triangle^{+}$$\longrightarrow$$u_{1}\,$$w_{1}\,$$\,w_{2}$$a_{2}\,$$a_{1}\,$$\,a_{4}$$\,a_{3}$$\,v$$\triangle^{+}$$\longrightarrow$$u_{1}\,$$w_{1}\,$$\,w_{2}$$a_{2}\,$$a_{1}\,$$\,a_{4}$$\,a_{3}$$\,v$

(IXb) Now suppose that there is no edge between any two neighbours of $u_{j}$
for $j\in\\{1,2\\}$. Let $w_{1},w_{2}$ be the two least-labelled neighbours of
$u_{1}$ distinct from $a_{1}$. We want to apply Lemma 2.2(ii) to the graph
$G^{(-)}:=G-\\{a_{1}a_{2}\\}$ with the edge $a_{1}a_{2}$ deleted, setting
$v=u_{1}$ and $R=\\{a_{1},w_{1},w_{2}\\}$ with $r_{1}=a_{1}$. Suppose that
Lemma 2.2(ii) succeeds in identifying a $\triangle^{+}$-switch
$(G^{(-)},\widetilde{G}^{(-)})$ such that $\widetilde{G}^{(-)}$ contains a
triangle on the vertices $a_{1},u_{1},z$ for some vertex $z\not\in D$. Let
$\widetilde{G}$ denote the graph on $\mathcal{G}_{n,\boldsymbol{d}}$ obtained
by inserting the edge $a_{1}a_{2}$ in $\widetilde{G}^{(-)}$. Then
$(G,\widetilde{G})$ is a $\triangle$-switch which can be applied to $G$. From
$\widetilde{G}$, we can perform the two $\triangle$-switches described in
Lemma 2.1 case (IV), to exchange the switch edges. Then from the resulting
graph, apply the inverse of the $\triangle$-switch $(G,\widetilde{G})$ to
“unplant” the triangle and produce the graph $H$. This gives a simulation path
of length 4.

(IXc) Finally we assume that there is no edge between any two neighbours of
$u_{j}$, for $j\in\\{1,2\\}$, but that Lemma 2.2(ii) did not succeed when
applied to the graph $G^{(-)}:=G-\\{a_{1}a_{2}\\}$ with $v=u_{1}$,
$R=\\{a_{1},w_{1},w_{2}\\}$ and $r_{1}=a_{1}$. (As above, we assume that
$w_{1},w_{2}$ are the two least-labelled neighbours of $u_{1}$ distinct from
$a_{1}$.) In particular, this implies that $G^{(-)}$ has a 5-cycle $C$ which
contains the path $a_{1}u_{1}w_{1}$, but $G^{(-)}$ does not have any 4-cycle
which contains the path $a_{1}u_{1}w_{j}$ for $j\in\\{1,2\\}$. The same
properties are true for $G$. Since $a_{1}$ has degree 2 in $G^{(-)}$, the
5-cycle $C$ must be $a_{1}u_{1}w_{1}zu_{2}$ for some vertex $z$. Note that
$u_{1}z$ cannot be an edge of $G$, or we are in case (IXa), and $w_{2}u_{2}$
cannot be and edge of $G$ as this would give rise to a 4-cycle
$a_{1}u_{1}w_{2}u_{2}$ in $G^{(-)}$ containing the path $a_{1}u_{1}w_{2}$.
Hence we can perform the following $\triangle$-switch in $G$ to plant a
triangle on $u_{1},w_{1},z$.

$u_{1}$$a_{1}$$\,w_{2}$$w_{1}\,$$\,u_{2}$$z$$\triangle^{+}$$\longrightarrow$$u_{1}$$a_{1}$$\,w_{2}$$w_{1}\,$$\,u_{2}$$z$

Then we have the situation in (IXa), where $u_{2}$ and its neighbours are
temporarily unimportant. The three $\triangle$-switches given in case (IXa)
perform the required switch, and from the resulting graph we apply the inverse
of the $\triangle$-switch which planted $u_{1}w_{1}w_{2}$, reaching the graph
$H$. This gives a simulation path of length five.∎

The proof of Theorem 1.1 combines Lemmas 2.1 and 2.3 and the fact that the
switch chain is irreducible on $\mathcal{G}_{n,\boldsymbol{d}}$ for all
graphical degree sequences $\boldsymbol{d}$ (see [38, 51]).

##  3 The asymptotic distribution of $t(G)$

We denote the Poisson distribution with mean $\mu$ by $\textrm{Pois}(\mu)$
and, if the random variable $X$ has this distribution, we write in standard
notation $X\thicksim_{d}\textrm{Pois}(\mu)$ or
$\mathcal{L}(X)=\textrm{Pois}(\mu)$. We wish to determine the approximate
distribution of $t(G)$ for large $n$, so we first give an appropriate
definition of distributional approximation in this context, which has wider
applicability. We note that the traditional approach to distributional
approximation, particularly in Statistics, has been through limit
distributions, usually with little or no error estimation.

###  3.1 Distributional approximation

Let $\mathcal{X}_{n}$ be a sequence of discrete state spaces, and let
$X_{n},X^{\prime}_{n}$ be random variables on $\mathcal{X}_{n}$ such that
$\mathcal{L}(X_{n})=p_{n},\mathcal{L}(X^{\prime}_{n})=p^{\prime}_{n}$. We will
say that $X_{n}$ _approximates $X^{\prime}_{n}$ asymptotically_ if
$p^{\prime}_{n}(A)=p_{n}(A)+o(1)$ for all $A\subseteq\Sigma$ as $n\to\infty$,
and we will denote this by $X^{\prime}_{n}\thickapprox_{d}X_{n}$. If $X_{n}$
has a known distribution, $\textrm{Pois}(\mu)$ say, we also write
$X^{\prime}_{n}\thickapprox_{d}\textrm{Pois}(\mu)$. This notation for
distributional approximation is taken from [46], but was used only informally
there.

i.e.

$\max_{A\subseteq\mathcal{X}}\big{|}\Pr(X^{\prime}_{n}\in A)-\Pr(X_{n}\in
A)\big{|}=o(1).$

This involves a known metric on distributions, the total variation distance,
$\mathrm{d}_{\mathrm{TV}}(p^{\prime}_{n},p_{n})$, as defined in (2). So
$X^{\prime}_{n}\thickapprox_{d}X_{n}$ (and vice versa) if the total variation
distance

$\mathrm{d}_{\mathrm{TV}}(p^{\prime}_{n},p_{n})=\tfrac{1}{2}\sum_{x\in\mathcal{X}_{n}}|p^{\prime}_{n}(x)-p_{n}(x)|=o(1)\mbox{\,\
as\ \,}n\to\infty.$

This relation is symmetric, reflexive and transitive, since
$\mathrm{d}_{\mathrm{TV}}$ is a metric. However, transitivity holds only over
a finite number of applications, since we must preserve the $o(1)$ term. So
this is only a local equivalence relation on sequences
$(\mathcal{X}_{n},p_{n})$.

This definition is not new. Janson [32] used the term “asymptotic equivalence”
for this relationship between sequences of random variables, using the
notation $(X_{n})\cong(X^{\prime}_{n})$. However, the focus in [32] is on the
case where both $X^{\prime}_{n}$ and $X_{n}$ are unknown distributions, and
the equivalence indicates a stronger relationship than contiguity. There the
relationship between $X_{n}$ and $X^{\prime}_{n}$ is symmetrical. Here we
assume $X_{n}$ has a known distribution which approximates the unknown
distribution of $X^{\prime}_{n}$, so the relationship is not symmetrical.
Also, as we have noted above, this is not a true equivalence relation.
Therefore, we prefer the above terminology and notation.

Note that requiring only $p^{\prime}_{n}(x)=p_{n}(x)+o(1)$ for all
$x\in\mathcal{X}_{n}$ is not a useful notion of approximation. For example,
suppose $\mathcal{X}_{n}=[2n]$, $p_{n}(x)=1/n$ ($x\in[n]$),
$p^{\prime}_{n}(x)=1/n$, ($x\in[2n]\setminus[n]$). Then $X_{n}$ approximates
$X^{\prime}_{n}$ in this weaker sense, since $p^{\prime}_{n}(x)=p_{n}(x)\pm
1/n$. However, $\mathrm{d}_{\mathrm{TV}}(p_{n},p^{\prime}_{n})=1$ for all $n$,
so this does not seem a reasonable approximation.

Though we will only use it in the discrete case, the approach to
distributional approximation outlined above can be extended to arbitrary
probability measures, as is done in [32]. It was initially developed for
Normal approximations [50], but later for other distributions (e.g. [10, 45,
46]). The methods used have been elementary (e.g. [47]), coupling arguments
(e.g. [45]), Stein’s method [50, 6] and semigroup methods (e.g. [37, 49]). The
aim has been to quantify errors in limit distributions in Statistics, or to
quantify rates of convergence to these limit distributions, rather than to
quantify asymptotic approximations.

We will use only elementary methods, but with an alternative criterion, which
we now show is equivalent to the definition above.

######  Lemma 3.1.

$X_{n}\thickapprox_{d}X^{\prime}_{n}$ if and only if there is a set
$S_{n}\subset\mathcal{X}_{n}$ such that, as $n\to\infty$,
$p^{\prime}_{n}(x)=(1+o(1))p_{n}(x)$ for all $x\notin S_{n}$ and
$\max\\{p_{n}^{\prime}(S_{n}),p_{n}(S_{n})\\}=o(1)$.

###### Proof.

If $S_{n}$ exists then there exist sequences $0<\delta_{n},\epsilon_{n}=o(1)$
so that $|p^{\prime}_{n}(x)-p_{n}(x)|<\delta_{n}p_{n}(x)$ for $x\notin S_{n}$
and $\max\\{p_{n}^{\prime}(S_{n}),p_{n}(S_{n})\\}<\epsilon_{n}$. Hence

$\mathrm{d}_{\mathrm{TV}}(p_{n},p^{\prime}_{n})<\epsilon_{n}+\delta_{n}\sum_{x\notin
S_{n}}p_{n}(x)<\epsilon_{n}+\delta_{n}=o(1),$

so $X_{n}\thickapprox_{d}X^{\prime}_{n}$.

Conversely, if $X_{n}\thickapprox_{d}X^{\prime}_{n}$ then there is a sequence
$0<\eta_{n}=o(1)$ such that
$\mathrm{d}_{\mathrm{TV}}(p_{n},p^{\prime}_{n})<\eta_{n}$. Let
$\epsilon_{n}=\sqrt{\eta_{n}}=o(1)$ and define

$S_{n}=\left\\{x\in\mathcal{X}_{n}:\frac{|p^{\prime}_{n}(x)-p_{n}(x)|}{\max\\{p_{n}(x),p^{\prime}_{n}(x)\\}}\geq\epsilon_{n}\right\\}.$

Then

$\epsilon_{n}^{2}>\mathrm{d}_{\mathrm{TV}}(p_{n},p^{\prime}_{n})\geq\epsilon_{n}\sum_{x\in
S_{n}}\max\\{p_{n}(x),p^{\prime}_{n}(x)\\}\geq\epsilon_{n}\max\\{p_{n}(S_{n}),p^{\prime}_{n}(S_{n})\\},$

so $\max\\{p_{n}(S_{n}),p^{\prime}_{n}(S_{n})\\}<\epsilon_{n}=o(1)$.

If $x\notin S_{n}$, then we have
$|p^{\prime}_{n}(x)-p_{n}(x)|<\epsilon_{n}\max\\{p_{n}(x),p^{\prime}_{n}(x)\\}$.
By taking $n$ sufficiently large, we can assume that
$\epsilon_{n}<\nicefrac{{1}}{{2}}$, and hence $p^{\prime}_{n}(x)\leq
2p_{n}(x)$ for all $x\not\in S_{n}$. For all such $n$ and all $x\not\in
S_{n}$, we conclude that
$p^{\prime}_{n}(x)/p_{n}(x)\in(1-2\epsilon_{n},1+2\epsilon_{n})$, and hence
$p^{\prime}_{n}(x)\in(1\pm\delta_{n})p_{n}$ where
$\delta_{n}=2\epsilon_{n}=o(1)$ as $n\to\infty$. This completes the proof. ∎

This formulation also gives explicit bounds on errors. In one direction, we
can take $\eta_{n}=\epsilon_{n}+\delta_{n}$, while in the other we can take
$\epsilon_{n}=\sqrt{\eta_{n}}$ and $\delta_{n}=2\sqrt{\eta_{n}}$.

Note that $X^{\prime}_{n}\thickapprox_{d}X_{n}$ does not imply that
$X^{\prime}_{n},X_{n}$ have exactly the same properties. Suppose
$Y_{n}=h_{n}(X_{n}),Y^{\prime}_{n}=h_{n}(X^{\prime}_{n})$ for a function
$h_{n}:\mathcal{X}_{n}\to\mathbb{C}$ (the complex numbers). Let
$\|h_{n}\|=\max_{x\in\mathcal{X}_{n}}|h_{n}(x)|$. Then we can only claim
$\mathbb{E}(Y^{\prime}_{n})\sim\mathbb{E}(Y_{n})$ if $h_{n}$ is uniformly
bounded in $n$ using this norm. This follows from the (easily proved)
inequality

$\big{|}\mathbb{E}[Y^{\prime}_{n}]-\mathbb{E}[Y_{n}]\big{|}\leq\|h_{n}\|\mathrm{d}_{\mathrm{TV}}(p_{n},p^{\prime}_{n}),$

with equality possible if
$h_{n}(x)=\textrm{sign}\big{(}p^{\prime}_{n}(x)-p_{n}(x)\big{)}$, where
$\textrm{sign}(x)\in\\{-1,0,1\\}$ (in the obvious way), so $\|h_{n}\|=1$
(unless $p^{\prime}_{n}=p_{n}$ and
$\mathrm{d}_{\mathrm{TV}}(p^{\prime}_{n},p_{n})=0$). Indeed, this equality is
another characterisation of $\mathrm{d}_{\mathrm{TV}}$. Note that the uniform
boundedness requirement includes $X_{n}$ itself, so care is needed.

As an example, suppose $\mathcal{X}_{n}=[n]$, $p_{n}=C_{n}/i^{2}$ ($i\in[n]$),
where $C_{n}\sim\pi^{2}/6$. (This example is related to the Cauchy
distribution.) However, $\mathbb{E}[X_{n}]=\Omega(\log n)\to\infty$ as
$n\to\infty$. The explanation is that $n$ is not a uniformly bounded function
of $n$. This is a known pathology in the limit theory of distributions. In
this example, $X^{\prime}_{n}$ converges pointwise to a fixed distribution,
but $\lim_{n\to\infty}\mathbb{E}[X^{\prime}_{n}]$ does not even exist.

In the limit distribution approach to approximation, we must restrict
attention to uniformly bounded functions. Here, if $h_{n}$ is not uniformly
bounded, we have the additional option of estimating the contribution to the
expectation from $S_{n}$, as we do below for Poisson approximations.

However, if $X^{\prime}_{n}\thickapprox_{d}X_{n}$ for real-valued random
variables, then $X_{n}$ and $X^{\prime}_{n}$ do have the same characteristic
function $\mathbb{E}(e^{itx})$ in the limit as $n\to\infty$, since
$|e^{itx}|=1$ for all real $t$ and $x$. This could be used, for example, to
prove asymptotic Normality of the Poisson approximations below in the limit
distribution sense.

However, note that we cannot use this idea of approximation to compare
discrete distributions with continuous distributions. Discrete points have
measure zero in a continuous distribution, so we always have
$\mathrm{d}_{\mathrm{TV}}(X_{n},X^{\prime}_{n})=1$. Thus, any definition of
approximation in this context must use a weaker metric than
$\mathrm{d}_{\mathrm{TV}}$. For real-valued random variables, the usual choice
is the _Kolmogorov metric_
$\max_{x\in\mathbb{R}}|F_{n}(x)-F^{\prime}_{n}(x)|$, where
$F_{n},F^{\prime}_{n}$ are the respective distribution functions of
$X_{n},X^{\prime}_{n}$. Thus, the asymptotic Normal results for triangles
proved in [18] are valid for larger values of $\mu$ than the asymptotic
Poisson results proved here, but they are much weaker approximations. In fact,
the indirect method of proof used in [18] does not seem to allow for any
quantification of errors.

In our application below we compare the distribution of $t(G)$, the number of
triangles in $G$ chosen uniformly at random from
$\mathcal{G}_{n,\boldsymbol{d}}$, to a Poisson distribution with the same mean
$\mu$.

The maximum number of triangles in $G\in\mathcal{G}_{n,\boldsymbol{d}}$ is
$M_{2}/6$, so we take $\mathcal{X}_{n}=\\{0,1,\ldots,M_{2}/6\\}$. Then
$X^{\prime}_{n}$ will be the the number of triangles $t(G)$ when $G$ is chosen
uniformly at random from $\mathcal{G}_{n,\boldsymbol{d}}$,
$\mu=\mathbb{E}_{G}[t(G)]$ and $X_{n}\thicksim_{d}\textrm{Pois}(\mu)$. We will
take $S_{n}=\\{G:t(G)>t_{0}\\}$, for a suitably large $t_{0}$, to be
determined. Thus $S_{n}$ is the tail of the distribution of $t(G)$. Then we
will show that $X_{n}\thickapprox_{d}\textrm{Pois}(\mu)$, when $\mu$ is a
small enough unbounded function of $n$. We divide the proof by analysing first
“small” values of $t<t_{0}$ in section 3.2 and then “large” values of
$t>t_{0}$ in section 3.2. Thus, in section 3.2 we consider $G\notin S_{n}$,
and in section 3.3 we consider $G\in S_{n}$.

###  3.2 Small $t$

For $t=0,\ldots,M_{2}/6$, let
$\mathcal{N}_{t}=\\{G\in\mathcal{G}_{n,\boldsymbol{d}}:t(G)=t\\}$ be the set
of graphs with exactly $t$ triangles, and let $N_{t}=|\mathcal{N}_{t}|$. We
will use $\mathcal{G}_{t}$ to denote an element of $\mathcal{N}_{t}$ chosen
uniformly at random.

Our proof will be based on the _switchings_ technique of McKay [41] and others
and the conditional probability estimates of Gao and Ohapkin [21]. For
reference, we paraphrase [21, Corollary 2] as follows. Let
$G\in\mathcal{G}_{n,\boldsymbol{d}}$ and
$H^{+}\in\mathcal{G}_{n,\boldsymbol{d}^{\prime}}$, where
$\boldsymbol{d}^{\prime}<\boldsymbol{d}$, and let
$M^{\prime}=\sum_{i=1}^{n}d^{\prime}_{i}=2|E(H^{+})|$. Then, if $G$ is chosen
uniformly from $\mathcal{G}_{n,\boldsymbol{d}}$,

$\Pr(uv\in G|H^{+}\subset
G)=\bigg{(}1+O\Big{(}\frac{d_{1}^{2}}{M-M^{\prime}}\Big{)}\bigg{)}\frac{(d_{u}-d^{\prime}_{u})(d_{v}-d^{\prime}_{u})}{M-M^{\prime}+(d_{u}-d^{\prime}_{u})(d_{v}-d^{\prime}_{u})}.$
(8)

In our application $H^{+}$ will be a subgraph $H_{t}$ of $G$ containing
exactly $t$ triangles with $t=o(M)$, which will imply that the error term in
(8) is $O(d_{1}^{3}/M)$.

######  Remark 1.

In [21] there is also a subgraph $H^{-}$, edge-disjoint from $H^{+}$, which is
conditioned on being absent from $G$. Since we make no use of this, we omit
it. Also, we make the $1+o(1)$ term explicit in (8), since we iterate these
estimates and hence exponentiate this term. We start with $H^{+}=\emptyset$,
$\boldsymbol{d}^{\prime}=\mathbf{0}$, so $H^{+}$ remains small relative to
$G$.

######  Remark 2.

Note that (8) is essentially the unconditioned estimate on the graph which
results from deleting the edges of $H_{t}$ from $G$, as might be expected
using the configuration model for graphs with given degree sequences.

We apply these estimates with the switching method, as follows. Consider the
set $S_{t}^{+}$ of $\triangle^{+}$-switches from $\mathcal{N}_{t}$ which
create exactly one triangle and destroy none. Also define the set of the
inverses of these $\triangle^{+}$-switches, namely the set $S_{t+1}^{-}$ of
$\triangle^{-}$-switches from $\mathcal{N}_{t+1}$ which delete exactly one
triangle and create none. Let $s_{t}^{+}=|S_{t}^{+}|$ and
$s_{t}^{-}=|S_{t}^{-}|$. Then we have

$N_{t}\,\mathbb{E}[s_{t}^{+}\mid\mathcal{G}_{t}]\,=\,N_{t+1}\,\mathbb{E}[s_{t+1}^{-}\mid\mathcal{G}_{t+1}],$
(9)

from which we can estimate $N_{t+1}/N_{t}$. We note that McKay and co-authors
have considerably generalised this switchings idea, for example in [29], but
here we only require the simple version given above.

Recall that $\mu(\boldsymbol{d})=M_{2}^{3}/6M^{3}$. We first prove a claim
made in section 1.1 above.

######  Lemma 3.2.

If $d_{1}^{2}=o(M)$ and $M_{2}\geq M$ then $\mathbb{E}[t(G)]\sim\mu.$

###### Proof.

Using (8), and calculations similar to cases (a) and (b) of Lemma 3.3 below,
we have, for triangles $i,j,k$,

$\mathbb{E}[t(G)]=\Big{(}1+O\Big{(}\frac{d_{1}^{2}}{M}\Big{)}\Big{)}^{3}\,\sum_{\begin{subarray}{c}i,j,k=1\\\
\text{distinct}\end{subarray}}^{n}\,\frac{d_{i}(d_{i}-1)d_{j}(d_{j}-1)d_{k}(d_{k}-1)}{6M^{3}}\sim\frac{M_{2}^{3}}{6M^{3}}=\mu,$
(10)

where the divisor 6 counts permutations of $i,j,k$ representing the same
triangle. The exponent 3 on the error term in (10) results from 3 uses of (8)
and replacing the 3 occurrences of $M+O(d_{1}^{2})$ with $M$. A relative error
of $O(d_{1}^{2}/M_{2})$ arises from the terms where $i,j,k$ are not distinct:
these terms arise in $M_{2}^{3}$ but are not present in the original sum.
Therefore we need to assume $M_{2}=\Omega(M)$, but we make the stronger
assumption $M_{2}\geq M$. Note that ∎

We have $\mu(\boldsymbol{d})=M_{2}^{3}/6M^{3}\geq\nicefrac{{1}}{{6}}$ under
our assumption $M_{2}\geq M$, so $\mu=\Omega(1)$ as $n\to\infty$.

Note that the numerator in the summation in (10) is independent of the order
in which the edges of the triangle are exposed, and depends only on its degree
structure. This observation is true for all small subgraphs, and we use it
below without further comment.

######  Lemma 3.3.

If $td_{1}^{3}=o(M)$ and $M_{2}\geq M$ then
$\mathbb{E}[s_{t}^{+}\mid\mathcal{G}_{t}]\,=\,\big{(}1+O(td_{1}^{3}/M)\big{)}\,6M\mu$.

###### Proof.

We first give an estimate of $\mathbb{E}[s_{t}^{+}\mid\mathcal{G}_{t}]$, and
then show that it is asymptotically tight. A $\triangle^{+}$-switch
corresponds to a path of length 5 in $G$, which we will denote by $P_{5}$,
though we make no assumptions about other possible edges between its vertices.
The $\triangle^{-}$-switch corresponding to this $P_{5}$ starts with a
triangle on its 3 middle edges, and a disjoint edge between its end vertices.
We will label these as illustrated below.

$i$$j$$k$$\ell$$m$$i$$j$$k$$\ell$$m$

Then our initial estimate is the number of $P_{5}$’s, where we will
temporarily ignore other restrictions:

$\displaystyle\mathbb{E}[s_{t}^{+}\mid\mathcal{G}_{t}]$
$\displaystyle\leq\big{(}1+O(d_{1}^{2}/M)\big{)}^{4}\,\sum_{\begin{subarray}{c}i,j,k,\ell,m=1\\\
\text{distinct}\end{subarray}}^{n}\frac{d_{i}(d_{i}-1)\,d_{j}(d_{j}-1)\,d_{k}(d_{k}-1)\,d_{\ell}\,d_{m}}{M^{4}}$
$\displaystyle\leq\big{(}1+O(d_{1}^{2}/M)\big{)}\,\frac{M_{2}^{3}M^{2}}{M^{4}}=6M\mu,$
(11)

where the expression in the summation is obtained using (8) with
$H_{t}=\emptyset$.

The estimate (11) is an upper bound because we have ignored conditions that
should be imposed and which reduce the expectation. We will now refine this by
considering each possible overestimate in turn. This will give us a lower
bound on the expectation which matches the upper bound asymptotically for
small enough $t$ and $d_{1}$.

  1. (a)

First, we should have $i\neq j\neq k\neq l\neq m$. There are $\binom{5}{2}=10$
possible first-order equalities in (11), and we claim that each of these gives
rise to a $1+O(d_{1}^{2}/M)$ error factor. Consider, for example if $i=j$. If
the other vertices are distinct, then (11) becomes

$\sum_{i,k,l,m=1}^{n}\frac{d_{i}^{2}(d_{i}-1)^{2}d_{k}(d_{k}-1)d_{l}d_{m}}{M^{4}}\leq\frac{d_{1}^{2}M_{2}^{2}M^{2}}{M^{4}}=\frac{d_{1}^{2}M\mu}{M_{2}}\leq
d_{1}^{2}\mu.$

Comparing this with (11) gives the claim. So overall the effect is no worse
than a $(1+O(d_{1}^{2}/M))^{10}=1+O(d_{1}^{2}/M)$ factor. Note that higher-
order equalities are automatically included, in fact over-counted, in these
calculations.

  2. (b)

We have used $M$ in the denominator in (11) rather than the $M-M^{\prime}$
from (8). In fact, $H_{t}$ is a set of $t$ triangles, so $M^{\prime}\leq 6t$,
so the denominator in (8) is at most $M+d_{1}^{2}$, and at least $M-6t$. So
using $M$ produces a $(1+O(t+d_{1}^{2})/M)^{4}=1+O(t+d_{1}^{2})/M$ error
factor in (11).

  3. (c)

We have not considered the effect of $H_{t}$ on the calculation of the
quantity
$M^{\prime}_{2}=\sum_{i=1}^{n}(d_{i}-d^{\prime}_{i})(d_{i}-d^{\prime}_{i}-1)$
which corresponds to $M_{2}$ on $G$. We have

$M_{2}\geq
M^{\prime}_{2}=\sum_{i=1}^{n}(d_{i}-d^{\prime}_{i})(d_{i}-d^{\prime}_{i}-1)\geq\sum_{i=1}^{n}d_{i}(d_{i}-1)-2d_{1}\sum_{i=1}^{n}d^{\prime}_{i}\geq
M_{2}-12td_{1},$

So using $M_{2}$ produces a $(1+O(td_{1})/M_{2})^{3}=1+O(td_{1})/M$ error
factor in (11).

  4. (d)

We wish to ensure that almost all $P_{5}$’s do not contain an edge of $H_{t}$.
We claim that these give rise to a $1+O(td_{1}^{2}/M)$ error factor. Consider,
for example if $ij\in E(H_{t})$. Then (11) becomes

$\displaystyle 2\sum_{ij\in
E(H_{t})}\sum_{k,l,m=1}^{n}\frac{(d_{i}-1)(d_{j}-1)d_{k}(d_{k}-1)d_{l}d_{m}}{M^{3}}$
$\displaystyle\leq\frac{2td_{1}^{2}M_{2}M^{2}}{M^{3}}=\frac{2td_{1}^{2}M_{2}^{3}M^{2}}{M^{3}M_{2}^{2}}$
$\displaystyle=\frac{12td_{1}^{2}\mu M^{2}}{M_{2}^{2}}=O(td_{1}^{2}\mu).$

Again, comparing this with (11) gives the claim. Since there are only four
edges, the overall the effect is no worse than a factor
$(1+O(td_{1}^{2}/M))^{4}=1+O(td_{1}^{2}/M)$.

Since it avoids edges of $H_{t}$, the $\triangle^{+}$-switch move has
probability at most $O(td_{1}^{2}\mu)/M$ of breaking any triangle.

  5. (e)

We need to ensure that the edges $jk$ and $\ell m$ are absent in almost all
$P_{5}$’s, so that they give a valid $\triangle^{+}$-switches. We claim that
these give rise to a $1+O(d_{1}^{5}/M)$ error factor. Consider $jk$. The
expected number of $P_{5}$’s in which it is present is at most

$\sum_{i,j,k,l,m=1}^{n}\frac{d_{i}(d_{i}-1)d_{j}(d_{j}-1)(d_{j}-2)d_{k}(d_{k}-1)(d_{k}-2)d_{l}d_{m}}{M^{5}}\leq\frac{d_{1}^{2}M_{2}^{3}M^{2}}{M^{5}}=O(\mu
d_{1}^{2}),$

and comparison with (11) gives the claim. The calculation for $\ell m$ is
similar.

  6. (f)

We wish to ensure that the edges $jk$ and $\ell m$ are not edges of $H_{t}$.
Otherwise, the $P_{5}$ will not give a valid $\triangle^{+}$-switch. If $jk\in
H_{t}$, then (11) becomes

$\displaystyle 2\sum_{jk\in E(H_{t})}\sum_{k,l,m=1}^{n}$
$\displaystyle\frac{d_{i}(d_{i}-1)(d_{j}-2)(d_{k}-2)d_{l}d_{m}}{M^{4}}\leq\frac{2td_{1}^{2}M_{2}M^{2}}{M^{4}}=\frac{2td_{1}^{2}M_{2}}{M^{2}}$
$\displaystyle=\frac{12td_{1}^{2}\mu}{M}=O(td_{1}^{2}\mu/M).$

and, if $\ell m\in E(H_{t})$, (11) becomes

$\displaystyle 2\sum_{lm\in E(H_{t})}\sum_{k,l,m=1}^{n}$
$\displaystyle\frac{d_{i}(d_{i}-1)d_{j}(d_{j}-2)d_{k}(d_{k}-1)(d_{\ell}-1)(d_{m}-1)}{M^{4}}\leq\frac{2td_{1}^{2}M_{2}^{3}}{M^{4}}$
$\displaystyle=\frac{12td_{1}^{2}\mu}{M}=O(td_{1}^{2}\mu/M).$

Note that these events will not even occur asymptotically if
$td_{1}^{2}\mu=o(M)$, since their expectation is then $o(1)$.

  7. (g)

We must ensure that almost all $P_{5}$’s create only one triangle. The
expected number in which the new edge $jk$ will create a second triangle
$(hjk)$ is at most

$\displaystyle\sum_{h,i,j,k,l,m=1}^{n}$
$\displaystyle\frac{d_{h}(d_{h}-1)d_{i}(d_{i}-1)d_{j}(d_{j}-1)(d_{j}-2)d_{k}(d_{k}-1)(d_{k}-2)d_{l}d_{m}}{M^{6}}$
$\displaystyle\leq\frac{d_{1}^{2}M_{2}^{4}M^{2}}{M^{6}}=\frac{6d_{1}^{2}\mu
M_{2}}{M}=O(\mu d_{1}^{3}).$

The expected number of $P_{5}$’s in which the new edge $\ell m$ will create
any triangle $(hlm)$ is at most

$\displaystyle\sum_{h,i,j,k,l,m=1}^{n}$
$\displaystyle\frac{d_{i}(d_{i}-1)d_{j}(d_{j}-1)d_{k}(d_{k}-1)d_{\ell}(d_{\ell}-1)d_{h}(d_{h}-1)d_{m}(d_{m}-1)}{M^{6}}$
$\displaystyle=\frac{M_{2}^{6}}{M^{6}}=\mu^{2}=O(\mu d_{1}^{3}).$

Combining these two cases gives an error factor $1+O(d_{1}^{3}/M)$.

The effect of combining all these cases gives an overall error factor which we
may bound by $1+O(d_{1}^{2}(d_{1}+t)/M)=1+O(td_{1}^{3}/M)$, the critical cases
arising from (d) and (g). Note also that (d) implies that almost all valid
$\triangle^{+}$-switches give rise to a triangle in $\mathcal{G}_{t+1}$ which
is edge-disjoint from $H_{t}$. ∎

We now consider the $\triangle^{-}$-switches reversing these
$\triangle^{+}$-switches.

######  Lemma 3.4.

If $td_{1}^{2}=o(M)$, then
$\mathbb{E}[s_{t+1}^{-}\mid\mathcal{G}_{t}]\,=\,(1+O(td_{1}^{3}/M))6(t+1)M.$

###### Proof.

We must choose a triangle $(ijk)$ and a labelling of it as $i,j,k$, which can
be done in $6$ ways. Then, from the proof of Lemma 3.3 we may assume that the
triangle $(ijk)$ is edge-disjoint from any other since, from case (d) in the
proof of Lemma 3.3, this will be true for all but a proportion
$O(td_{1}^{2}/M)$. So deleting $jk$ will delete exactly one triangle. Note
that we could show that $(ijk)$ will be vertex-disjoint from $H_{t}$, but
edge-disjointness is sufficient here.

Deleting $\ell m$ will delete no triangles if $\ell m\notin E(H_{t})$. So
there are at most $M$, and at least $M-2|E(H_{t})|$ choices for $\ell m$. So
there are $(1-O(t/M))M$ choices. If $\ell j\in E(H_{t})$ or $mk\in E(H_{t})$,
the $\triangle^{-}$-switch will be invalid, but again case (d) in the proof of
Lemma 3.4 implies that only a proportion $O(td_{1}^{2}/M)$ of
$\triangle^{-}$-switches will $\mathcal{G}_{t+1}$ can be invalid for this
reason. Otherwise, the expected number of triangles $(\ell jh)$ created by
inserting $\ell j$ will be at most

$\sum_{h=1}^{n}\frac{d_{h}(d_{h}-1)(d_{j}-2)(d_{\ell}-1)}{M^{2}}\leq\frac{d_{1}^{2}M_{2}}{M^{2}}\leq\frac{d_{1}^{3}}{M}.$

So the error factor in $\mathbb{E}[s_{t+1}^{-}\mid\mathcal{G}_{t}]$ is
$1+O(d_{1}^{3}/M)$. The same calculation for $mk$ gives the same error, so the
total effect will remain $1+O(d_{1}^{3}/M)$.

Combining the error estimates we have an overall $1+O(td_{1}^{3}/M)$ factor,
completing the proof. ∎

We can now show that $t(G)$ is asymptotically Poisson for a large range of
$d_{1}$.

######  Theorem 3.1.

Let $t_{0}=\min\\{\sqrt{M/d_{1}^{3}},\omega(n)d_{1}^{3}\\}$ for any function
$\omega(n)\to\infty$ as $n\to\infty$. Then, if $t=o(t_{0})$, $\Pr(t(G)=t)\sim
e^{-\mu}\mu^{t}/t!$.

###### Proof.

It follows from Lemmas 3.3 and 3.4 and (9) that

$\frac{N_{t+1}}{N_{t}}=(1+O(td_{1}^{3}/M))\frac{\mu}{t+1},$

and, iterating this through $t,t-1,\ldots,1$,

$\frac{\Pr(t(G)=t)}{\Pr(t(G)=0)}=\frac{N_{t}}{N_{0}}=(1+O(td_{1}^{3}/M))^{t}\frac{\mu^{t}}{t!}=(1+O(t^{2}d_{1}^{3}/M))\frac{\mu^{t}}{t!}\sim\frac{\mu^{t}}{t!},$
(12)

if $t^{2}d_{1}^{3}=o(M)$, which is $t=o(\sqrt{M/d_{1}^{3}}$), so is valid for
$t\leq t_{0}$. Summing (12)

$\frac{\Pr(t\leq
t_{0})}{\Pr(t=0)}\sim\sum_{t=0}^{t_{0}}\frac{\mu^{t}}{t!}=e^{\mu}-\sum_{t=t_{0}+1}^{\infty}\frac{\mu^{t}}{t!}.$
(13)

Now $d_{1}^{3}=o(t_{0})$ implies $\mu=o(t_{0})$, so the term on the right is

$\sum_{t=t_{0}+1}^{\infty}\frac{\mu^{t}}{t!}<\sum_{t=t_{0}+1}^{\infty}\left(\frac{o(t_{0})}{t_{0}}\right)^{t}\sim
o(1)^{t_{0}}=o(1).$

In section 3.3 below, we show that $\Pr(t\leq t_{0})=1-o(1)$. So, since
$\mu=\Omega(1)$, (13) gives

$\frac{\Pr(t\leq t_{0})}{\Pr(t=0)}=\frac{1-o(1)}{\Pr(t=0)}\sim
e^{\mu}-o(1)=(1-o(1))e^{\mu}.$ (14)

From (14), $\Pr(t=0)\sim e^{-\mu}$, and so (12) gives $\Pr(t(G)=t)\sim
e^{-\mu}\mu^{t}/t!$, and so $t(G)$ is approximately Poiss($\mu$). ∎

The conditions of Theorem 3.1 are satisfied if $d_{1}=o(M^{1/9})$ and
$d_{1}^{3}=o(t_{0})$. This will be satisfied if $d_{1}=o(n^{1/9})$ and
$t=o(n^{1/3})$.

######  Remark 3.

Gao [18] has shown a Normal limit distribution for $t(G)$ for $d$-regular
graphs as $n\to\infty$, in the form $(t-\mu)/\sqrt{\mu}\stackrel{{\scriptstyle
d}}{{\to}}\mathrm{N}(0,1)$, provided $d\to\infty$ and $d=O(\sqrt{n})$. This is
a limit for $\textrm{Pois}(\mu)$ as $\mu\to\infty$, but whether Poisson
approximation holds for such large $d$ is an open question.

###  3.3 Large $t$

Here we will use much weaker bounds, since our goal is only to show that the
tail of the distribution of $t(G)$ has very small probability in the
equilibrium distribution, provided $\lambda$ and $d_{1}$ is small enough.
Then, in combination with Theorem 3.1, we will have shown that
$t(G)\thickapprox_{d}\textrm{Pois}(\mu)$, in the notation of section 3.1. In
fact, we prove something stronger, that the contribution of the tail to
$\mathbb{E}[\lambda^{t(G)}]$ is negligible for small enough $\lambda$ and
$d_{1}$. We will use this in section 3.4 to show that
$t(G)\thickapprox_{d}\textrm{Pois}(\lambda\mu)$ for sufficiently small
$\lambda$ and $d_{1}$. Specifically, when $\lambda>1$ we will assume that

$d_{1}\log\lambda=o(\log n)\quad\text{ and }\quad d_{1}^{3}=o(M).$

A lower bound on the number $s^{-}(G)$ of valid $\triangle^{-}$-switches from
$G\in\mathcal{G}_{i}$ which create no triangle is given by taking any triangle
and any edge at distance at least 3 from the triangle. There are at least
$M-6(d_{1}-1)^{3}$ choices for this directed edge. If $d_{1}=o(M^{1/3})$, this
is $(1-o(1))M$. So $s^{-}(G)\geq(6-o(1))tM$ since we must choose a triangle
edge and a direction, and
$s^{-}(\mathcal{N}_{t})=\sum_{G\in\mathcal{N}_{t}}s^{-}(G)\geq(6-o(1))tMN_{t}$.
No triangles are created by any of these $\triangle^{-}$-switches, but may be
destroyed by removal of the switch edges. So we destroy at least 1 and at most
$2(d_{1}-1)$ triangles. These bounds are tight, since every edge might lie in
a $(d_{1}+1)$-clique, as is the case for graphs comprising $n/(d_{1}+1)$
cliques of size $(d_{1}+1)$.

So all the $\triangle^{-}$-switches from $G\in\mathcal{N}_{t}$ lead to a
$G^{\prime}\in\mathcal{N}^{\prime}_{t}=\bigcup_{1\leq i\leq
2(d_{1}-1)}\mathcal{N}_{t-i}$. Suppose a proportion $\gamma_{i}$ leads to
$\mathcal{N}_{t-i}$, so $\sum_{i=1}^{2(d_{1}-1)}\gamma_{i}=1$, and note that
hence $\sum_{i=1}^{2(d_{1}-1)}\gamma_{i}N_{t-i}\leq\max\\{N_{t-i}:1\leq i\leq
2(d_{1}-1)\\}=N_{t^{\prime}}$, for some $t-2(d_{1}-1)\leq t^{\prime}\leq t-1$.
Observe that we will have $t^{\prime}=t-2(d_{1}-1)$ if $G$ is $d_{1}$-regular
and $t=nd_{1}(d_{1}-1)/6$, so the lower bound can be tight. Moreover, van der
Hoorn et al. [27] show that almost all $d_{1}$-regular graphs have almost all
their triangles in large cliques for $t(G)=\Omega(n)$, so the analysis we give
here may be difficult to improve significantly.

An upper bound on the number $s^{+}(G^{\prime})$ of valid
$\triangle^{+}$-switches from any $G^{\prime}\in\mathcal{N}^{\prime}_{t}$ is
the total number of possible switches, valid or not. There are at most
$\sum_{i=1}^{n}2\binom{d_{i}}{2}(d_{1}-1)^{2}=M_{2}(d_{1}-1)^{2}$
possibilities, so there are at most $M_{2}(d_{1}-1)^{2}N_{t^{\prime}}$ valid
$\triangle^{+}$-switches from $\mathcal{N}^{\prime}_{t}$ to $\mathcal{N}_{t}$.
Consequently, we must have
$M_{2}(d_{1}-1)^{2}N_{t^{\prime}}\geq(6-o(1))tMN_{t}$, and hence

$\frac{N_{t}}{N_{t^{\prime}}}\leq(1+o(1))\frac{M_{2}(d_{1}-1)^{2}}{6tM}\leq\frac{\hat{\mu}}{t},$

where $\hat{\mu}=(d_{1}-1)^{3}/6\geq M_{2}^{3}/M^{3}=\mu$, since $M_{2}\leq
M(d_{1}-1)$. Note that equality holds if $G$ is $d_{1}$-regular.

We can iterate this to give

$\frac{N_{t}}{N_{0}}\leq\frac{\hat{\mu}^{\ell}}{tt^{\prime}\cdots
t^{(\ell-1)}},$

where $t^{(j-1)}-t^{(j)}\leq 2d_{1}-2$ for $0<j<\ell$, $t^{(0)}=t$,
$t^{(\ell)}=0$. The weakest bound results when $t^{(j-1)}-t^{(j)}=2d_{1}-2$
and $\ell=t/(2d_{1}-2)$, giving

$\frac{N_{t}}{N_{0}}\leq\frac{\hat{\mu}^{t/(2d_{1}-2)}}{(2d_{1}-2)^{t/(2d_{1}-2)}(t/(2d_{1}-2))!}=\frac{(\hat{\mu}/(2d_{1}-2))^{t/(2d_{1}-2)}}{(t/(2d_{1}-2))!}<\bigg{(}\frac{e\hat{\mu}}{t}\bigg{)}^{t/(2d_{1}-2)},$

using the bound $(t/(2d_{1}-2))!>(e^{-1}t/(2d_{1}-2))^{t/(2d_{1}-2)}$ from
Stirling’s approximation. It follows that, for
$G\in\mathcal{G}_{n,\boldsymbol{d}}$,

$\Pr(t(G)=t)<\bigg{(}\frac{e\hat{\mu}}{t}\bigg{)}^{t/(2d_{1}-2)}.$

We will assume that $d_{1}=o(n^{1/9})$ and $t_{0}=\Omega(n^{1/3})$ from
section 3.2. However, we must also assume
$\lambda^{2d_{1}-2}\hat{\mu}=o(t_{0})$, which we use to imply
$\lambda^{2d_{1}-2}\hat{\mu}\leq t_{0}/e^{2}$. This assumption is true if
$d_{1}\log\lambda=o(\log n)$, which is a stronger constraint on $d_{1}$ unless
$\lambda\sim 1$. Then

$\displaystyle\Pr(t\geq t_{0})\ <$ $\displaystyle\
\sum_{t=t_{0}}^{M_{2}/6}\lambda^{t}\bigg{(}\frac{e\hat{\mu}}{t}\bigg{)}^{t/(2d_{1}-2)}<\
\sum_{t=t_{0}}^{\infty}\bigg{(}\frac{e\lambda^{2d_{1}-2}\hat{\mu}}{t}\bigg{)}^{t/(2d_{1}-2)}$
$\displaystyle<$ $\displaystyle\ \sum_{t=t_{0}}^{\infty}e^{-t/(2d_{1}-2)}\ =\
e^{-t_{0}/(2d_{1}-2)}/\big{(}1-e^{-1/(2d_{1}-2)}\big{)}$ $\displaystyle<$
$\displaystyle\ 2d_{1}e^{-t_{0}/2d_{1}}\ =\ O(e^{-\Omega(n^{1/4})}),$

using the inequality $1-x<e^{-x}$ for $x>0$.

If $\lambda=1$, the uniform distribution $\pi^{\prime}$, the constraint
$d_{1}\log\lambda=o(\log n)$ disappears and the tail bound is small provided
$\hat{\mu}=d_{1}^{3}/6=o(t_{0})$, i.e $d_{1}=o(\sqrt[3]{t_{0}})$. So we can
take $d_{1}=o(n^{1/9})$ and $t=o(n^{1/3})$, as claimed in section 3.2.
However, if $\lambda>1$ is a constant, we must have $d_{1}=o(\log n)$.

###  3.4 Equilibrium distribution of the chain

In Sections 3.2, 3.3, we have shown that
$t(G)\thickapprox_{d}\textrm{Pois}(\mu)$ under the uniform distribution
$\pi^{\prime}$ on $\mathcal{G}$, provided $d_{1}=o(n^{1/9})$. Since we know
$t(G)$ is approximately Poisson, we can derive its distribution under the
equilibrium distribution $\pi$ of the chain on $\mathcal{G}$, provided that
$d_{1}\log\lambda=o(\log n)$, so that the tail of the distribution has
probability $o(1)$, as shown in section 3.3. For the uniform distribution
$\pi^{\prime}$, using the discussion in section 1.2, we have

$\mathbb{E}_{\mathrm{\pi^{\prime}}}[\lambda^{t}]\sim\sum_{k\geq
0}\lambda^{k}e^{-\mu}\frac{\mu^{k}}{k!}\ \sim e^{(\lambda-1)\mu}\,\sum_{k\geq
0}\frac{(\mu\lambda)^{k}}{k!}e^{-\mu\lambda}=e^{(\lambda-1)\mu}.$

as claimed above. Hence, for the Metropolis distribution $\pi$, if
$t(G)=o(n^{\epsilon})$,

${\Pr}_{\pi}(t(G)=s)=\frac{\lambda^{s}\Pr_{\mathrm{\pi^{\prime}}}(t(G)=s)}{\mathbb{E}_{\mathrm{\pi^{\prime}}}[\lambda^{t}]}\sim\frac{\lambda^{s}e^{-\mu}\mu^{s}/s!}{e^{(\lambda-1)\mu}}=\frac{e^{-\lambda\mu}(\lambda\mu)^{s}}{s!}.$

Hence we have shown that $t(G)\thickapprox_{d}\textrm{Pois}(\lambda\mu)$ under
$\pi$. In particular the mean is $\lambda\mu$, so the expected number of
triangles increases by a factor $\lambda$. So, in order to increase the number
of triangles as far as possible, we should take $\lambda$ as large as
possible, under the constraint $d_{1}\log\lambda=o(\log n)$.

###  3.5 Assumptions on the degree sequence

In our asymptotic results we made the assumption that $M_{2}\geq M$. We will
now prove that this is equivalent to having average degree $\bar{d}\geq 2$.
For our Markov chain analysis the condition $\bar{d}\geq 2$ is automatically
satisfied, since we assume $d_{n}\geq 3$.

######  Lemma 3.5.

$M_{2}\geq M$ if and only if $\bar{d}\geq 2$.

###### Proof.

We have

$0\leq\sum_{i=1}^{n}(d_{i}-\bar{d})^{2}=\sum_{i=1}^{n}d_{i}^{2}-n\bar{d}^{2}=M_{2}+M-M\bar{d}=M_{2}-M(\bar{d}-1),$

so $M_{2}\geq M$ if $\bar{d}\geq 2$. For the converse, suppose that $M_{2}<M$.
Let $n_{j}$ be the number of vertices with degree $j$, for all $j\geq 1$. Then

$M_{2}-M=-n_{1}+\sum_{j\geq 3}j(j-2)n_{j}<0,$

and

$M=n_{1}+2n_{2}+\sum_{j\geq 3}jn_{j}\leq n_{1}+2n_{2}+\sum_{j\geq
3}j(j-2)n_{j}<2n_{1}+2n_{2}\leq 2n.$

So $\bar{d}<2$, completing the proof. ∎

For our Markov chain $\bar{d}\geq 2$ is automatically satisfied, since we
assume $d_{n}\geq 3$. However, our asymptotic distributions are valid for
$\bar{d}\geq 2$. The excluded graphs are rather uninteresting. They have a
preponderance of components which are paths, as we see from the following.

######  Lemma 3.6.

$M_{2}\geq M$ for any connected graph $G$ which is not a path.

###### Proof.

If $G$ is not a path or a cycle, then $d_{1}\geq 3$. A cycle has $\bar{d}=2$,
so $M_{2}\geq M$ from Lemma 3.5. Otherwise, we can construct $G$ from a
3-star, a graph with degree sequence $(3,1,1,1)$, by successively adding edges
and vertices. For a 3-star, $M_{2}=M=6$. Now, if we add an edge between
vertices of degrees $d_{i}$ and $d_{j}$, $M\leftarrow M+2$, and

$M_{2}\leftarrow
M_{2}+(d_{i}+1)d_{i}+(d_{j}+1)d_{j}-d_{i}(d_{i}-1)-d_{j}(d_{j}-1)=M_{2}+2(d_{i}+d_{j})\geq
M_{2}+2,$

with equality only if we add an edge from a vertex of degree $d_{i}=1$ to a
new vertex of degree 0. Otherwise the inequality is strict. The claim now
follows by induction. ∎

If $G$ is a path $P_{\ell}$ with $\ell$ vertices, then $M=2(\ell-1)$ and
$M_{2}=2(\ell-2)$, so $M-M_{2}=2$. Thus, if $M>M_{2}$, Lemma 3.6 implies that
most components must be paths.

##  4 Rapid mixing

In this section we prove Theorem 1.2 using the two-stage direct canonical path
construction method, restated above as Theorem 1.3.

###  4.1 The simulation path

Recall the definitions from section 1.4. Let $\mathcal{M}$ denote the
$\triangle$-switch chain and $\mathcal{M}^{\prime}$ denote the switch chain.
Let $P,\pi$ be the transition matrix and stationary distribution of the
$\triangle$-switch chain $\mathcal{M}$, and similarly define $P^{\prime}$,
$\pi^{\prime}$ with respect to the switch chain $\mathcal{M}^{\prime}$. Recall
that $\pi^{\prime}$ is uniform on $\mathcal{G}_{n,\boldsymbol{d}}$ while
$P^{\prime}(G,H)=1/(3a(\boldsymbol{d}))$ if $G\neq H$ and $P^{\prime}(G,H)>0$,
where $a(\boldsymbol{d})$ is defined in (1). We assume that the switch chain
$\mathcal{M}^{\prime}$ is rapidly mixing on $\mathcal{G}_{n,\boldsymbol{d}}$,
and let $\Gamma^{\prime}$ be a set of canonical paths for
$\mathcal{M}^{\prime}$ with polynomial congestion. Using results of Sinclair
[48], Guruswami [26, Theorem 4.9] proved that under mild conditions on
$\mathcal{M}^{\prime}$, a polynomial bound on the mixing time of
$\mathcal{M}^{\prime}$ implies the existence of an appropriate set
$\Gamma^{\prime}$ of canonical paths with
$\rho(\Gamma^{\prime})\leq\text{poly}(n)$.

In section 2 we constructed a set

$\Sigma=\\{\sigma_{GH}\mid(G,H)\in E(\mathcal{M}^{\prime})\\}$

of $(\mathcal{M},\mathcal{M}^{\prime})$-simulation paths. Recall the
parameters defined in (5). The maximum simulation path length is
$\ell(\Sigma)=5$ from Lemmas 2.1 and 2.3. Next we prove an upper bound on the
parameter $B(\Sigma)$, which measures the maximum number of simulation paths
containing any given $\triangle$-switch.

######  Lemma 4.1.

Let $\boldsymbol{d}$ be a graphical degree sequence with $d_{1}\geq
d_{2}\geq\cdots\geq d_{n}\geq 3$ and let $\Sigma$ be the set of
$(\mathcal{M},\mathcal{M}^{\prime})$-simulation paths defined in section  _2_.
Then

$B(\Sigma)\leq 20d_{1}^{2}\,(2M+d_{1}^{2})$

where $M=M(\boldsymbol{d})=\sum_{j\in[n]}d_{j}$.

###### Proof.

Let $e=(X,Y)$ be a transition of the $\triangle$-switch chain. We want an
upper bound on the number of simulation paths $\sigma_{GH}$ which contain $e$,
where $(G,H)$ is a transition of the switch chain. To do this, we will work
through the cases (I)–(IX) from Lemmas 2.1 and 2.3. We will not try to
optimise the bounds we determine. We are only interested here in correctness
and, to a lesser extent, simplicity.

Let $D=\\{a_{1},a_{2},a_{3},a_{4}\\}$ denote the vertices involved in the
switch $(G,H)$ that we need to identify.

  * (I)

In Case (I) we have $(G,H)=(X,Y)$ which happens in exactly 1 way.

  * (II)

In Case (II), the simulation path has length 2 and only involves the vertices
in $D$. So the simulation path is $G,G_{1},H$ and in $G_{1}$, the edges
$a_{1}a_{4}a_{2}a_{3}$ are present and the switch edges $a_{1}a_{2}$,
$a_{1}a_{3}$, $a_{2}a_{4}$, $a_{3}a_{4}$ are all absent. Therefore, if
$(X,Y)=(G,G_{1})$ then we know $G=X$ and $H$ is obtained from $G_{1}$ by
replacing edges $a_{1}a_{4}$, $a_{2}a_{3}$ with $a_{1}a_{3}$, $a_{2}a_{4}$
(the only perfect matching of $D$ not seen in either $G$ or $G_{1}$). This can
be done in exactly one way. By a similar argument, if $(X,Y)=(G_{1},H)$ then
there is exactly one way to reconstruct $G$. So overall, there are 2
possibilities for $(G,H)$ if $(X,Y)$ is involved in a simulation path in Case
(II).

  * (III)

There are exactly 2 possibilities arising from Case (III), using a very
similar argument to that used for Case (II).

  * (IV)

The simulation path defined in Case (IV) has length 2, so it is $G,G_{1},H$
for some $G_{1}$. Each $\triangle$-switch in the path involves 3 vertices in
$D$ and one vertex not in $D$. (Note that in the second subcase, the vertex
$w$ of the triangle on $a_{1},u,w$ is not involved in either of the
$\triangle$-switches in the simulation path.) There are 4 ways to label the
vertices involved in a given $\triangle$-switch, and in each case the
remaining vertex of $D$ is a neighbour of one of the four vertices involved in
the $\triangle$-switch. Hence there are at most $4d_{1}$ ways to label all
vertices in $D$ or involved in the $\triangle$-switch, and using these
vertices we can uniquely construct $H$ from $(G,G_{1})$, or uniquely construct
$G$ from $(G_{1},H)$. Hence there are at most $8d_{1}$ possibilities for
$(G,H)$ if $(X,Y)$ is involved in a simulation path in Case (IV).

  * (V)

The simulation path in Case (V) has length 4, so it is $G,G_{1},G_{2},G_{3},H$
for some graphs $G_{1},G_{2},G_{3}$. If $(X,Y)=(G,G_{1})$ then one of the
edges switched out is the diagonal $a_{1}a_{4}$, the the other edge switched
out is $uv$ where $u,v\not\in D$. Then $a_{2}$ is a common neighbour of of
$a_{1},u,v$ in $G$, and $a_{3}$ is a common neighbour of $a_{4},u,v$ in $G$.
So there are 2 choices for which of the removed edges is $a_{1}a_{4}$ and at
most $d_{1}^{2}$ ways to choose the unordered pair $\\{a_{2},a_{3}\\}$. From
$G=X$ and this information we can recover $H$. (Note that by symmetry we do
not need to multiply by a factor of 2 to decide which vertex of the edge
$a_{1}a_{4}$ is $a_{1}$. The same argument works for the final
$\triangle$-switch in the simulation path.

Next, if $(X,Y)=(G_{1},G_{2})$ then the $\triangle$-switch involves the
vertices $a_{1},a_{2},a_{3},a_{4}$, removing the edges $a_{1}a_{2}$,
$a_{3}a_{4}$ which are present in $G$ and inserting the diagonals
$a_{1}a_{4}$, $a_{2}a_{3}$. Hence we know that $H[D]$ is given by the only
perfect matching of $D$ not seen in either $X$ or $Y$. To recover $G$ from $X$
we must know the vertices $u,v$ which are both common neighbours of $a_{2}$
and $a_{3}$, so there are at most $d_{1}^{2}$ choices for $u,v$. The same
argument holds if $(X,Y)=(G_{2},G_{3})$. Overall, there are at most
$6d_{1}^{2}$ ways that $(X,Y)$ could be involved in a simulation path in Case
(V).

  * (VI)

The simulation path in Case (VI) has length 4. Each $\triangle$-switch in this
simulation path involves four of the vertices $a_{1},a_{2},a_{3},a_{4},u,v,w$.
There are 4 ways to label the vertices involved in each $\triangle$-switch in
this path, and then the remaining 3 vertices can be chosen in at most
$d_{1}^{3}$ ways, since the subgraph induced by
$\\{a_{1},a_{2},a_{3},a_{4},u,v,w\\}$ is connected at each step. Once the
identities of these vertices are known, from any $\triangle$-switch on the
simulation path, we can construct $(G,H)$ uniquely. It follows that there are
at most $16d_{1}^{3}$ ways that $(X,Y)$ could be involved in a simulation path
in Case (VI).

  * (VII)

The simulation path in Case (VII) has length 4, consisting of a triangle-
planting $\triangle$-switch, then the simulation path from Case (IV) in the
resulting graph, then the “unplanting” $\triangle$-switch. Lemma 2.2 is used
to choose the triangle-planting $\triangle$-switch, with $v=a_{1}$ and
$R\subseteq\mbox{N}(a_{1})\setminus D$. If $(X,Y)$ is the triangle-planting
$\triangle$-switch $(G,\widetilde{G})$ then $X=G$. If (in the application of
Lemma 2.2) $\ell=4$ then the triangle-planting $\triangle$-switch involves one
vertex from $D$ and three vertices outside $D$. There are 4 ways to label the
vertices involved in the $\triangle$-switch, which identifies $a_{1}$ (say).
Then there at most $d_{1}$ ways to choose $a_{2}$ from the neighbours of
$a_{1}$, and at most $M$ ways to choose the vertices $(a_{3},a_{4})$. Using
these vertices we can construct $H$. So there are at most $4d_{1}M$ ways that
$(X,Y)$ can be the triangle-planting $\triangle$-switch when $\ell=4$, and the
same bound holds when $\ell=5$.

However, if $\ell\geq 6$ then the triangle-planting $\triangle$-switch does
not involve $a_{1}$, but involves two neighbours $u_{1},u_{2}$ of $a_{1}$ (the
neighbours form a triangle with $a_{1}$ after the $\triangle$-switch). Here
there are 2 choices for the edge $u_{1}u_{2}$ which is inserted by the
$\triangle$-switch, then at most $d_{1}^{2}$ choices for $(a_{1},a_{2})$ and
at most $M$ choices for $(a_{3},a_{4})$. Once these vertices are known, we can
construct $H$ from $G$. There are at most $2d_{1}^{2}M$ ways that $(X,Y)$ can
be the triangle-planting switch when $\ell\geq 6$. Hence, overall there are at
most $8d_{1}M+2d_{1}^{2}M$ ways that $(X,Y)$ could be the triangle-planting
$\triangle$-switch in Case (VII). The same bound holds for the “unplanting”
$\triangle$-switch at the end of the simulation path, and we must also add the
$8d_{1}$ choices that arise if $(X,Y)$ is used as the second or third
$\triangle$-switch in the simulation path. (We multiply $8d_{1}$ by three as
there are three possibilities for $\ell$, as described above.) As a grand
total, there are at most

$4d_{1}^{2}M+16d_{1}M+24d_{1}$

possiblities for $(G,H)$ if $(X,Y)$ is part of a simulation path in Case
(VII).

  * (VIII)

In subcase (VIIIa), the triangle-planting $\triangle$-switch involves two
vertices from $D$, say $a_{1},a_{3}$, and two vertices outside $D$. There are
4 ways to label the vertices involved in the $\triangle$-switch and then at
most $d_{1}^{2}$ ways to choose $(a_{2},a_{4})$. So if $(X,Y)$ is the
triangle-planting $\triangle$-switch in subcase (VIIIa) then there are at most
$4d_{1}^{2}$ options for $(G,H)$, as $G=X$ and $H$ can be constructed from $G$
using these known vertices. The same bound holds for the unplanting
$\triangle$-switch in subcase (VIIIa), and again we have at most $8d_{1}$
options from the second or third $\triangle$-switch in the simulation path,
giving at most $8d_{1}^{2}+8d_{1}$ choices for $(G,H)$ from subcase (VIIIa).

In subcase (VIIIb), the triangle-planting $\triangle$-switch involves exactly
one vertex from $D$, say $a_{1}$, and three vertices outside $D$. One of the
vertices involved in the triangle-planting $\triangle$-switch is a neighbour
of $a_{3}$, so there are at most $4d_{1}^{3}$ ways to identify all vertices in
the triangle-planting $\triangle$-switch and all vertices in $D$. The same
bound holds for the unplanting $\triangle$-switch, and again we must include
the bound $8d_{1}$ to cover the second and third $\triangle$-switches in the
simulation path. Hence there are at most $8d_{1}^{3}+8d_{1}$ choices for
$(G,H)$ if $(X,Y)$ is part of a simulation path in subcase (VIIIb).

Overall, there are at most

$8d_{1}^{3}+8d_{1}^{2}+16d_{1}$

choices for $(G,H)$ if $(X,Y)$ is part of a simulation path in case (VIII).

  * (IX)

In subcase (IXa), the simulation path has length 3, so it is $G,G_{1},G_{2},H$
for some graphs $G_{1},G_{2}$. (Here we do not plant a triangle.) The first
$\triangle$-switch involves one vertex of $D$, say $a_{3}$, and a neighbour of
$a_{1}$. So there are at most $4d_{1}^{3}$ ways to identify all vertices in
the $\triangle$-switch as well as $(a_{1},a_{2},a_{4})$. Here $G=X$ and we can
construct $H$ using the vertices already identified. The second
$\triangle$-switch $(G_{1},G_{2})$ involves the four vertices of $D$, with
$u_{1}$ a common neighbour of $a_{1}$ and $a_{3}$ (say) and where
$u_{1}w_{1}w_{2}v$ is a path in $G_{1}$. Hence there are at most $2d_{1}^{4}$
ways to identify each of the vertices of $D\cup\\{u_{1},w_{1},w_{2}\\}$. Using
this we can construct $G$ from $G_{1}$ and then construct $H$. Finally, the
third switch involves exactly one vertex from $D$, say $a_{3}$, but now it is
possible that $a_{2}$ and $a_{4}$ belong to a different component than $a_{3}$
in both $G_{2}$ and $H$. Since $H=Y$, there are at most $4d_{1}M$ ways to
identify the vertices of $D$ and then construct $G$ from $H$. Overall there
are most $4d_{1}M+2d_{1}^{4}+4d_{1}^{3}$ choices for $(G,H)$ if $(X,Y)$ is
part of a simulation path in subcase (IXa).

In subcase (IXb), we call Lemma 2.2 to identify a triangle-planting switch
$(G,\widetilde{G})$. Then from $\widetilde{G}$ we perform two
$\triangle$-switches as described in Case (IV), then we “unplant” the triangle
by performing the inverse $\triangle$-switch in the resulting graph. There are
several possibilities which we must analyse:

    * –

If Lemma 2.2 uses a 4-cycle which includes the path $a_{1}u_{1}w_{j}$ for
$j\in\\{1,2\\}$, then the triangle-planting $\triangle$-switch does not
involve any vertex of $D$, but involves a neighbour of $a_{1}$, say. Hence
there are at most $4d_{1}^{2}M$ ways to identify the vertices of $D$. Since
$G=X$, this allows us to construct $H$.

    * –

If $a_{1}u_{1}w_{j}$ is not part of a 4-cycle or 5-cycle ($j=1,2$) then the
triangle-planting $\triangle$-switch involves $a_{1}$, and hence there are at
most $4d_{1}M$ ways to identify the vertices of $D$ and hence construct $H$
from $G=X$.

    * –

If $a_{1}u_{1}w_{j}$ is in a 5-cycle but is not in any 4-cycle, then the
triangle-planting $\triangle$-switch does not involve any element of $D$ but
it involves neighbours of $a_{1}$, say. So there are at most $4d_{1}^{2}M$
ways to identify the vertices of the $\triangle$-switch and of $D$, which
allows us to construct $H$ uniquely from $G=X$.

In each case, the same bounds hold for the final “unplanting”
$\triangle$-switch, and there are at most $8d_{1}$ choices for $(G,H)$ which
arise if $(X,Y)$ is the second or third $\triangle$-switch in the simulation
path. (We multiply $8d_{1}$ by 3 to account for the three possible situations
for $\ell$.) In total, this gives at most

$2(8d_{1}^{2}M+4d_{1}M)+24d_{1}=16d_{1}^{2}M+8d_{1}M+24d_{1}$

choices for $(G,H)$ when $(X,Y)$ is part of a simulation path in subcase
(IXb).

In subcase (IXc), we require a $\triangle$-switch to plant a triangle, say
$(G,\widetilde{G})$. The $\triangle$-switch involves no vertex from $D$ but
involves a neighbour of one vertex from $D$, say $a_{1}$. Here $G=X$ and there
are at most $4d_{1}^{2}M$ ways to identify the elements of the
$\triangle$-switch vertices and $D$, and hence construct $H$ from $G$. The
same bound holds for the final “unplanting” $\triangle$-switch. The other
three $\triangle$-switches in the simulation path match those in subcase
(IXa), and we proved above that there are at most
$4d_{1}M+2d_{1}^{4}+4d_{1}^{3}$ choices for $(G,H)$ if $(X,Y)$ is one of these
three $\triangle$-switches. This gives at most

$4d_{1}M+2d_{1}^{4}+4d_{1}^{3}+2(4d_{1}^{2}M)=8d_{1}^{2}M+4d_{1}M+2d_{1}^{4}+4d_{1}^{3}$

choices for $(G,H)$ when $(X,Y)$ is part of a simulation path in subcase
(IXc).

Hence overall, there are at most

$24d_{1}^{2}M+16d_{1}M+4d_{1}^{4}+8d_{1}^{3}+24d_{1}$

choices for $(G,H)$ if $(X,Y)$ is part of a simulation path in Case (IX).

Adding up contributions from every case, we see that a $\triangle$-switch
$(X,Y)$ can belong to the simulation path of at most

$28d_{1}^{2}M+32d_{1}M+4d_{1}^{4}+32d_{1}^{3}+14d_{1}^{2}+72d_{1}+5$

pairs $(G,G^{\prime})$. We can simplify this using the assumption that
$d_{1}\geq 3$, and the fact that $M\geq 2d_{1}$ (as can be seen by considering
a star $K_{1,d_{1}}$). This gives an upper bound of

$\left(28+\frac{32}{3}\right)d_{1}^{2}M+\left(4+\frac{32}{3}+\frac{14}{9}+\frac{72}{27}+\frac{5}{81}\right)d_{1}^{4}<20d_{1}^{2}\,(2M+d_{1}^{2}).$

This completes the proof. ∎

###  4.2 Modifying the chain

We can now combine the results bounds to prove Theorem 1.2.

We first show that, provided $\lambda>1$ and $\lambda,\mu$ are small enough,
then there is a $\nu(n)$ such that ${\Pr}_{\pi}(t>\nu)=o(n^{-r})$ for any
constant $r$, but $\lambda^{\nu}\leq n^{s}$ for some constant $s$. Then we can
restrict the chain to the region $t\leq\nu$, since we will almost never see a
$G$ with $t(G)>\nu$ in polynomial time.

From section 3 we know that $\Pr(t>\nu)\sim\Pr(X>\nu)$, where
$X\thickapprox_{d}\textrm{Pois}(\lambda\mu)$, provided
$d_{1}\log\lambda=o(\log n)$ and $\nu=o(d_{1}^{3})$.

Suppose $\lambda\mu\leq\log^{\alpha}n$, and $\nu=\log n/\log\log n$ for some
constant $0\leq\alpha<1$. Then $d_{1}\log\lambda=o(\log n)$ and, from above,

$\displaystyle{\Pr}_{\pi}(t>\nu)$
$\displaystyle<(\lambda\mu/\nu)^{\nu}<(\log^{\alpha}n\log\log n/\log n)^{\log
n/\log\log n}$ $\displaystyle=(\log\log n)^{-(1-\alpha)\log
n}=n^{-(1-\alpha)\log\log\log n}=o(n^{-r}),$

for any constant $r>0$. On the other hand,

$\lambda^{\nu}\leq(\log^{\alpha}n)^{\log n/\log\log n}=e^{\alpha\log
n}=n^{\alpha},$

for large enough $n$.

The simplest way to use this is to modify the chain so that the equilibrium
distribution is proportional to $\lambda^{\min\\{t,\nu\\}}$. This is easy to
do using detailed balance. The total variation distance of this distribution
from the original is $o(n^{-r})$ for all constant $r$, so it is polynomial-
time indistinguishable from the true Metropolised distribution $\pi$.

Then we have

$\frac{Z_{\lambda}(\boldsymbol{d})}{|\mathcal{G}_{n,\boldsymbol{d}}|}=\mathbb{E}_{\mathrm{u}}[\lambda^{t}]<\lambda^{\nu}\leq
n^{\alpha},\quad\mbox{and}\quad
R(\mathcal{M},\mathcal{M}^{\prime})\leq\lambda^{2\nu}\leq n^{2\alpha},$

for the above ranges of $\lambda$ and $\mu$ and where
$R(\mathcal{M},\mathcal{M}^{\prime})$ is given by (7). We now apply this to
the rapid mixing proof.

###### Proof.

Let $\tau_{\lambda}(\varepsilon)$ denote the mixing time of the
$\triangle$-switch chain with parameter $\lambda$. Suppose that the switch
chain is rapidly mixing on $\mathcal{G}_{n,\boldsymbol{d}}$ for all
$\boldsymbol{d}\in\mathcal{D}$, and let $\boldsymbol{d}\in\mathcal{D}$ have
length $n$. Hence we may assume (see for example Guruswami [26, Theorem 4.9])
that there exists a set of canonical paths $\Gamma^{\prime}$ for the switch
chain with congestion $\bar{\rho}(\Gamma^{\prime})$ bounded above by a
polynomial in $n$, say

$\bar{\rho}(\Gamma^{\prime})\leq q(n)$ (15)

for all $\boldsymbol{d}\in\mathcal{D}$ with length $n$.

We will bound the mixing time using (3). It follows from a result of Diaconis
and Saloff-Coste [15, p. 702] that the smallest eigenvalue of the
$\triangle$-switch chain satisfies

$(1+\mu_{N-1})^{-1}\leq\max_{H\in\mathcal{G}_{n,\boldsymbol{d}}}\frac{1}{2\,P_{\lambda}(H,H)}\leq
3/2,$ (16)

where $P_{\lambda}$ denotes the transition matrix of the $\triangle$-switch
chain with parameter $\lambda$. We will bound $\mu_{1}$ by applying the direct
two-step canonical path construction method (as restated in Theorem 1.3) using
the set of simulation paths $\Sigma$ defined in section 2.

It follows from Lemma 2.1 and Lemma 2.3 that

$\ell(\Sigma)=5.$ (17)

An upper bound for $B(\Sigma)$ was proved in Lemma 4.1. The simulation gap
$D(\mathcal{M},\mathcal{M}^{\prime})$, defined in (6), satisfies

$\displaystyle D(\mathcal{M},\mathcal{M}^{\prime})$
$\displaystyle=\max_{\begin{subarray}{c}uv\in E(\mathcal{M})\\\ zw\in
E(\mathcal{M}^{\prime})\end{subarray}}\frac{\pi^{\prime}(z)P^{\prime}(z,w)}{\pi(u)P_{\lambda}(u,v)}$
$\displaystyle=\max_{\begin{subarray}{c}uv\in E(\mathcal{M})\\\ zw\in
E(\mathcal{M}^{\prime})\end{subarray}}\frac{|\mathcal{G}_{n,\boldsymbol{d}}|^{-1}\,(3a(\boldsymbol{d}))^{-1}}{\lambda^{t(u)}\,Z_{\lambda}(\boldsymbol{d})^{-1}\,\min\\{1,\lambda^{t(v)-t(u)}\\}\,(3a(\boldsymbol{d}))^{-1}}$
$\displaystyle=\max_{uv\in
E(\mathcal{M})}\frac{|\mathcal{G}_{n,\boldsymbol{d}}|^{-1}\,Z_{\lambda}(\boldsymbol{d})}{\min\\{\lambda^{t(u)},\lambda^{t(v)}\\}}\
\leq\ \frac{Z_{\lambda}(\boldsymbol{d})}{|\mathcal{G}_{n,\boldsymbol{d}}|}$
$\displaystyle\leq n^{\alpha},$ (18)

from above. Note that the inequality in (18) above will be an equality if

$\min_{uv}\\{\lambda^{\min\\{t(u),\nu\\})},\lambda^{\min\\{t(v),\nu\\}}\\}=1.$

It is easy to see that this will be the case if
$\mathcal{G}_{n,\boldsymbol{d}}$ contains at least two graphs, such that one
of them is triangle-free.

Hence we have

$D(\mathcal{M},\mathcal{M}^{\prime})\,R(\mathcal{M},\mathcal{M}^{\prime})\leq
n^{\alpha}n^{2\alpha}=n^{3\alpha}.$

Using Theorem 1.3, Lemma 4.1 and (15)–(18), we conclude that there is a set
$\Gamma$ of canonical paths for the $\triangle$-switch chain with parameter
$\lambda$ such that the congestion of $\Gamma$ satisfies

$\displaystyle\bar{\rho}(\Gamma)\leq
D(\mathcal{M},\mathcal{M}^{\prime})\,R(\mathcal{M},\mathcal{M}^{\prime})|\,\ell(\Sigma)\,B(\Sigma)\,\bar{\rho}(\Gamma^{\prime})$
$\displaystyle\leq 100n^{3}d_{1}^{2}\,(2M+d_{1}^{2})\,q(n),$

using the assumption of the theorem for the final inequality. It follows from
(4) that $\mu\leq 1-1/\bar{\rho}(\Gamma)$ and we can upper bound the mixing
time using (3).

It can be proved, for example using the configuration model [8], that

$\log|\mathcal{G}_{n,\boldsymbol{d}}|\leq M\ln M$

where $M=M(\boldsymbol{d})=\sum_{j\in[n]}d_{j}$, as above. Furthermore, if
$\pi^{\ast}$ denotes the smallest stationary probability of the modified
$\triangle$-switch chain, then

$1/\pi^{\ast}=\hat{Z}_{\lambda}(\boldsymbol{d})=\sum_{G\in\Omega_{n,d}}\lambda^{\min(t(G),\nu)}\leq
Z_{\lambda}(\boldsymbol{d}),$

where $\hat{Z}_{\lambda}(\boldsymbol{d})$ is the normalisation factor for the
stationay distribution of the modified $\triangle$-switch chain. Hence (15)
implies that

$\log(1/\pi^{\ast})\leq M\log M+\alpha\log n.$

Putting all this together, using (3), (4) and (16), gives

$\tau_{\lambda}(\varepsilon)\leq
100n^{3\alpha}\,d_{1}^{2}\,(2M+d_{1}^{2})\,q(n)\,\big{(}M\ln M+\alpha\log
n+\ln(\varepsilon^{-1})\big{)}.$

Thus, the modified $\triangle$-switch chain with parameter $\lambda$ is
rapidly mixing for all $\boldsymbol{d}\in\mathcal{D}$, under the assumption
$\lambda\mu\leq\log^{\alpha}n$ for some $0<\alpha<1$. ∎

These results seem weak, since the assumption $\lambda\mu\leq\log^{\alpha}n$
is quite restrictive, but improvement requires a different approach to
analysing the Markov chain.

###  4.3 Slow mixing

It seems disappointing that we can only prove rapid mixing for rather small
values of $\mu$ and $\lambda$, but this is largely a consequence of the
Metropolisation. Consider a $d$-regular graph $G$ which consists of $k$
disjoint copies of $K_{d+1}$. (Note that these graphs are central to the
irreducibility proof in [13].) Then $G$ contains no paths of length 4, so no
$\triangle^{+}$-switch is possible. Any $\triangle^{-}$-switch must take one
edge from each of two disjoint copies of $K_{d+1}$, and hence will destroy
$2(d-1)$ triangles. So any change to $G$ will occur only with probability
$\lambda^{-2(d-1)}$. Suppose that $\lambda>1$ is any constant and
$d=\gamma\log n$, where $\gamma\to\infty$ as $n\to\infty$. Then, with high
probability, no change will occur within
$(1/\lambda)^{d}=n^{\gamma\log\lambda}$ steps of the chain, which is
superpolynomial.

There are exponentially few $d$-regular graphs of this form, as a fraction of
the set of all $d$-regular graphs on $n=kd$ vertices, but each such graph
gives a potential bottleneck for mixing. The small proportion suggests a
solution by “ignoring” these graphs in some way. Unfortunately, the difficulty
is not restricted to these graphs. Suppose we have only a single $K_{d+1}$
component. In order to break the $K_{d+1}$, we require the two vertices of a
non-edge in the remainder of the graph to have many common neighbours, at
least $d/4$, say. Then a $\triangle^{-}$-switch could create at most $d/2$
triangles, which is not enough to offset the $d-1$ triangles that have been
destroyed. If there are $o(n)$ triangles in the current graph, then we can
bound the probability of such a non-edge appearing in the graph by
$O(n^{d/4+2}(d/n)^{d/2})=o(n^{-d/5})$, which is exponentially small if
$d\to\infty$ with $n$. Thus all $\triangle^{-}$-switch’s involving the
$K_{d+1}$ will have exponentially small probability of acceptance, and hence
mixing will take exponential time.

Of course, the proportion of $d$-regular graphs with $n$ vertices and at least
one $K_{d+1}$ component is still small. But, if $t(G)=\Omega(n)$, it is shown
in [27] that $G$ contains many dense clique-like structures, called
pseudocliques, which would require many steps to disassemble. Therefore, it
seems unlikely that the $\triangle$-switch chain could generate regular graphs
with $\Omega(n)$ triangles in polynomial time, except possibly for small
constant $d$. Nevertheless, the chain may well be rapidly mixing for a wider
range of $\mu$ and $\lambda$ than we are able to prove here.

## References

  * [1] D. Allendorf, U. Meyer, M. Penschuck, H. Tran and N. Wormald (2022), Engineering uniform sampling of graphs with a prescribed power-law degree sequence, in Proc. Symposium on Algorithm Engineering and Experiments (ALENEX 2022), pp. 27–40.
  * [2] Z. Allen-Zhu, A. Bhaskara, S. Lattanzi, V. Mirrokni and L. Orecchia (2018), Expanders via local edge flips, in: _Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms_ (SODA 2016), pp. 259-–269.
  * [3] G. Amanatidis and P. Kleer (2020), Rapid mixing of the switch Markov chain for strongly stable degree sequences, _Random Struct. Algorithms_ 57, 637–657.
  * [4] A. Arman, P. Gao and N. Wormald (2019), Fast uniform generation of random graphs with given degree sequences, in _60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019_), pp. 1371–1379.
  * [5] T. Bannink, R. van der Hofstad and C. Stegehuis (2018), Switch chain mixing times and triangle counts in simple random graphs with given degrees, _Journal of Complex Networks_ 7, 210-–225.
  * [6] A. Barbour, L. Holst and S. Janson, _Poisson Approximation_ , Oxford University Press, 1992.
  * [7] M. Bayati, J.H. Kim and A. Saberi (2010), A sequential algorithm for generating random graphs, _Algorithmica_ 58, 860–910.
  * [8] B. Bollobás (1980), A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, _European Journal of Combinatorics_ 1, 311–316.
  * [9] S. Chatterjee, P. Diaconis and A. Sly (2011), Random graphs with a given degree sequence, _Annals of Applied Probability_ 21, 1400–1435.
  * [10] L. Chen (1975), Poisson approximation for dependent trials, _Annals of Probability_ 3, 534–-545.
  * [11] C. Cooper, M. Dyer and C. Greenhill (2007), Sampling regular graphs and a peer-to-peer network, _Combinatorics, Probability and Computing_ 16, 557–593.
  * [12] C. Cooper, M. Dyer and C. Greenhill (2019), Triangle-creation processes on cubic graphs, arXiv:1905.04490.
  * [13] C. Cooper, M. Dyer and C. Greenhill (2021), A triangle process on regular graphs, in _Proc. 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021)_ , Springer Lecture Notes in Computer Science, vol. 12757, pp. 310–323.
  * [14] C. Cooper, M. Dyer, C. Greenhill and A. Handley (2019), The flip Markov chain for connected regular graphs, _Discrete Applied Mathematics_ 254, 56–79.
  * [15] P. Diaconis and L. Saloff-Coste (1993), Comparison theorems for reversible Markov chains, _Annals of Applied Probability_ 3, 696–730.
  * [16] P.L. Erdős, C. Greenhill, T.R. Mezei, I. Miklos, D. Soltész, L. Soukup (2022), The mixing time of the switch Markov chains: a unified approach. _European Journal of Combinatorics_ , 99, 103421.
  * [17] T. Feder, A. Guetz, M. Mihail and A. Saberi (2006), “A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks”, in: _Proc. 47th Annual IEEE Symposium on Foundations of Computer Science_ (FOCS 2006), pp. 69–76.
  * [18] P. Gao (2021), Triangles and subgraph probabilities in random regular graphs, Preprint: arXiv:2012.01492.
  * [19] P. Gao and N. Wormald (2017), Uniform generation of random regular graphs, _SIAM Journal of Computing_ 46, 1395–1427.
  * [20] P. Gao and C. Greenhill (2021), Mixing time of the switch Markov chain and stable degree sequences, _Discrete Applied Mathematics_ 291, 143–162.
  * [21] P. Gao and Y. Ohapkin (2022), Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity, _Random Structures & Algorithms_, to appear. Also arXiv:2007.02216.
  * [22] Z. Gao and N. Wormald (2008), Distribution of subgraphs of random regular graphs, _Random Structures & Algorithms_ 32, 38–48.
  * [23] S.M. Goodreau, J.A. Kitts and M. Morris (2009), Birds of a feather, or friend of a friend? Using exponential random graph models to investigate adolescent social networks, _Demography_ 46, 103–125.
  * [24] C. Greenhill and M. Sfragara (2018), The switch Markov chain for sampling irregular graphs and digraphs, _Theoretical Computer Science_ 719, 1–20.
  * [25] C. Greenhill (2021), Generating graphs randomly, in _Surveys in Combinatorics 2021_ , London Mathematical Society Lecture Note Series 470, Cambridge University Press, pp. 133–186.
  * [26] V. Guruswami (2000), Rapidly mixing Markov chains: A comparison of techniques (a survey). Unpublished manuscript. arXiv:1603.01512
  * [27] P. van der Hoorn, G. Lippner and E. Mossel (2022), Regular graphs with many triangles are structure, _Electronic Journal of Combinatorics_ 29, Art. P1.7.
  * [28] S. L. Hakimi (1962), On realizability of a set of integers as degrees of the vertices of a linear graph. I, _SIAM Journal on Applied Mathematics_ 10, 496–506.
  * [29] M. Hasheminezhad and B. McKay (2010), Combinatorial estimates by the switching method, _Contemporary Mathematics_ 531, 209–221.
  * [30] W. K. Hastings (1970), Monte Carlo sampling methods using Markov chains and their applications, _Biometrika_ 57, 97–109.
  * [31] V. Havel (1995), A remark on the existence of finite graphs (in Czech), Časopis Pro PěstovánıMatematiky 80, 477–480.
  * [32] S. Janson (2010), Asymptotic equivalence and contiguity of some random graphs, _Random Structures & Algorithms_ 36, 26–45.
  * [33] M. Jerrum, _Counting, Sampling and Integrating: Algorithms and Complexity_ , Birkhäuser, Basel, 2003.
  * [34] M. Jerrum and A. Sinclair (1989), Approximating the permanent, _SIAM J. Comput._ 18(6), 1149–1178.
  * [35] E.M. Jin, M. Girvan and M.E.J. Newman (2001), Structure of growing social networks, _Physical Review E_ 64, 046132.
  * [36] R. Kannan, P. Tetali and S. Vempala (1999), “Simple Markov chain algorithms for generating random bipartite graphs and tournaments”, _Random Structures & Algorithms_ 14, 293–308.
  * [37] L. Le Cam (1960), An approximation theorem for the Poisson binomial distribution, _Pacific J. Mathematics_ 10, 1181–1197.
  * [38] C. Lowcay, S. Marsland and C. McCartin (2013), Constrained switching in graphs: a constructive proof, in _2013 International Conference on Signal-Image Technology and Internet-Based Systems_ , pp. 599–604.
  * [39] I. Miklos, P. Erdős and L. Soukup (2013), “Towards random uniform sampling of bipartite graphs with given degree sequence”, _Electronic Journal of Combinatorics_ 20, #P16.
  * [40] P. Mahlmann and C. Schindelhauer (2005), Peer-to-peer networks based on random transformations of connected regular undirected graphs, in _Proc. 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005)_ , pp. 155–164.
  * [41] B. McKay (1985), Asymptotics for symmetric 0-1 matrices with prescribed row sums, _Ars Combin._ 19, 15–25.
  * [42] B. McKay (2010), Subgraphs of random graphs with specified degrees, _Proc. International Congress of Mathematicians (ICM 2010)_ , pp. 2489–2501.
  * [43] B. McKay, N. Wormald and B. Wysocka (2004), Short cycles in random regular graphs, _Electronic Journal of Combinatorics_ 11, #R66.
  * [44] N. Nishimura (2018), Introduction to reconfiguration, _Algorithms_ 11, 52.
  * [45] E. Pekoz, A. Rollin and N. Ross (2013), Total variation error bounds for geometric approximation, _Bernoulli_ 19, 610–-632.
  * [46] G. Reinert (2011), A short introduction to Stein’s method, Department of Statistics, University of Oxford.
  * [47] R. Serfling (1978), Some elementary results on Poisson approximation in a sequence of Bernouuli trials, _SIAM Review_ 20, 567–579.
  * [48] A. Sinclair (1992), Improved bounds for mixing rates of Markov chains and multicommodity flows, _Combinatorics, Probability and Computing_ 1, 351–370.
  * [49] J.M. Steele, Le Cam’s inequality and Poisson approximations, _American Mathematical Monthly_ 101, 48–54.
  * [50] C. Stein, (1986), _Approximate computation of expectations_ , Lecture Notes-Monograph Series vol. 7, Institute of Mathematical Statistics.
  * [51] R. Taylor (1981), Constrained switchings in graphs, in _Combinatorial Mathematics VIII_ (K.L. McAvaney, ed.), Springer Lecture Notes in Mathematics, vol. 884, pp. 314–336.
  * [52] K. Tikhomirov and P. Youssef (2022), Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, _Probability and Related Fields_ 185, to appear. Also arXiv:2007.02729.
  * [53] N. Wormald (2018), Asymptotic enumeration of graphs with given degree sequence, _Proc. International Congress of Mathematicians (ICM 2018)_ , pp. 3245–3264