Local semicircle law for random regular graphs

Introduction and results

Let $A$ be the adjacency matrix of a random $d$-regular graph on $N$ vertices. For fixed $d\geqslant 3$, it is well known that as $N\to\infty$ the empirical spectral measure of $A$ converges weakly to the Kesten-McKay law MR0109367 ; MR629617 , with density

Thus, the rescaled adjacency matrix $(d-1)^{-1/2}A$ has asymptotic spectral density

Clearly, $\varrho_{d}(x)\to\varrho(x)$ as $d\to\infty$, where $\varrho(x)\mathrel{\vbox{\hbox{.}\hbox{.}}}=\frac{1}{2\pi}\sqrt{[4-x^{2}]_{+}}$ is the density of Wigner’s semicircle law. The semicircle law is the asymptotic eigenvalue distribution of a random Hermitian matrix with independent (upper-triangular) entries (correctly normalized and subject to mild tail assumptions). From (1.2) it is natural to expect that, for sequences of random $d$-regular graphs such that $d\to\infty$ as $N\to\infty$ simultaneously, the spectral density of $(d-1)^{-1/2}A$ converges to the semicircle law. This was only proved recently MR2999215 (in MR3025715 it was also shown with the restriction that $d$ is only permitted to grow logarithmically in $N$).

In the study of universality of random matrix statistics, local versions of the semicircle law and its generalizations have played a crucial role; see for instance the survey MR2917064 . The local semicircle law is a far-reaching generalization of the weak convergence to the semicircle law mentioned above. First, the local law admits test functions whose support decreases with $N$ so that far fewer than $N$ eigenvalues are counted, ideally only slightly more than order $1$. (In contrast, weak convergence of probability measures applies only to macroscopic test functions counting an order $N$ eigenvalues). Second, the local law controls individual matrix entries of the Green’s function. Both of these improvements have proved of fundamental importance for applications. In particular, the local law established in this paper is a crucial input in 1505.06700-aop , where, with J. Huang, we prove that the local eigenvalue statistics of $A$ coincide with those of the Gaussian Orthogonal Ensemble; see also Section 1.4 below. For Wigner matrices, i.e. Hermitian random matrices with independent identically distributed upper-triangular entries, the semicircle law is known to hold down to the optimal spectral scale $1/N$, corresponding to the typical eigenvalue spacing, up to a logarithmic correction. In MR2999215 ; MR3025715 ; 1304.4343 ; 1305.1039 , it was shown that the semicircle law (for $d\to\infty$) or the Kesten-McKay law (for fixed $d$) holds for random $d$-regular graphs on spectral scales that are slightly smaller than the macroscopic scale $1$ (typically by a logarithmic factor; see Section 1.4 below for more details).

In this paper we show that $d$-regular graphs with degree $d$ at least $(\log N)^{4}$ obey the semicircle law down to spectral scales $(\log N)^{4}/N$. This scale is optimal up to the power of the logarithm.

From the perspective of random matrix theory, the adjacency matrix of a random $d$-regular graph is a symmetric random matrix with nonnegative integer entries constrained so that all row and column sums are equal to $d$. These constraints impose nontrivial dependencies among the entries. For example, if the sum of the first $k$ entries of a given row is $d$, the remaining entries of that row must be zero. Previous approaches to bypass this difficulty include local approximation of the random regular graph by a regular tree (for small degrees) and coupling to an Erdős-Rényi graph (for large degrees). These approaches have been shown to be effective for the study of several combinatorial properties, as well as global spectral properties of random regular graphs. However, they encounter serious difficulties when applied to the eigenvalue distribution on small scales (see Section 1.4 below for more details). Our strategy instead relies on a multiscale iteration of a self-consistent equation, in part inspired by the approach for random matrices with independent entries initiated in MR2481753 and significantly improved in a sequence of subsequent papers (again see Section 1.4 for details). In previous works on local laws for random matrices, independence of the matrix entries plays a crucial role in deriving the self-consistent equation (see e.g. MR3068390 for a detailed account). While the independence of the matrix entries can presumably be replaced by weak or short-range dependence, the dependence structure of the entries of random regular graphs is global. Thus, instead of independence, our approach uses the well known invariance of the random regular graph under a dynamics of local switchings, via a local resampling of vertex neighbourhoods. We believe that our strategy of local resampling, using invariance under a local dynamics combined with a multiscale iteration, is generally applicable to the study of the local eigenvalue distribution of random matrix models with constraints.

2. Random regular graphs

We establish the local law for the following three standard models of random $d$-regular graphs.

Let $N$ and $d$ be positive integers such that $Nd$ is even. The uniform model is the uniform probability measure on the set of all simple $d$-regular graphs on $[\![{1,N}]\!]$. (Here, simple means that the graph has no loops or multiple edges.) Equivalently, its adjacency matrix $A$ is uniformly distributed over the symmetric matrices with entries in $\{{0,1}\}$ such that all rows have sum $d$ and the diagonal entries are zero.

Permutation model

Let $N$ be a positive integer and $d$ an even positive integer. Let $\sigma_{1},\dots,\sigma_{d/2}$ be independent uniformly distributed permutations on $S_{N}$, the symmetric group of order $N$. The permutation model is the random graph on $N$ vertices obtained by adding an edge $\{i,\sigma_{\mu}(i)\}$ for each $i\in[\![{1,N}]\!]$ and $\mu\in[\![{1,d/2}]\!]$. Its adjacency matrix $A$ is given by

with the convention that $\sigma_{d-\mu}=\sigma_{\mu}^{-1}$ for $d/2+1\leqslant\mu\leqslant d$ in the second equality. All vertices have even degree, and in general the graph may have loops as well as multiple edges. Each loop contributes two to the degree of its incident vertex.

Matching model

Let $N$ be an even positive integer and $d$ a positive integer. Let $\sigma_{1},\dots,\sigma_{d}$ be independent uniformly distributed perfect matchings on $[\![{1,N}]\!]$. A perfect matching can be identified with a permutation of $S_{N}$ whose cycles all have length two. As in the permutation model, a graph on $[\![{1,N}]\!]$ is obtained by adding an edge $\{i,\sigma_{\mu}(i)\}$ for all $i\in[\![{1,N}]\!]$ and $\mu\in[\![{1,d}]\!]$. Thus, the corresponding adjacency matrix is again

Graphs of this model can have multiple edges but no loops. Their degree $d$ is arbitrary, but their number of vertices must be even.

The models introduced above include simple graphs (uniform model), graphs with loops and multiple edges (permutation model), and graphs with multiple edges but no loops (matching model). Throughout this paper, all statements apply to any of the above three models, unless explicitly stated otherwise. As discussed in Section 1.4 below, our approach is quite general, and applies to other models of random regular graphs as well. For brevity, however, we give the details for the three representative models introduced above.

We shall give error bounds depending on the parameter

In particular, for the uniform model, $D=d$ if $d\leqslant\sqrt{N}$, and for the permutation and matching models, $D=d$ if $d\leqslant N$. Throughout the paper, we make the tacit assumption $D\geqslant 1$, which leads to the conditions $d\leqslant N^{2/3}$ for the uniform model and $d\leqslant N^{2}$ for the permutation and matching models.

3. Main result

Our main result is stated in terms of the Green’s function (or the resolvent) of $H$, defined by

where $r\in$. Away from the two edges $z=\pm 2$ of the support of the semicircle law, i.e. for $|z\pm 2|\geqslant\varepsilon$ for some $\varepsilon>0$, the function $F$ is linearly bounded: $F_{z}(r)=O_{\varepsilon}(r)$. Near the edges, $F_{z}(r)\leqslant\sqrt{r}$ provides a weaker bound.

The condition $D\gg\xi^{2}$ in the statement of Theorem 1.1 implies the following restrictions on the degree of the graphs:

Thus, for the smallest possible degree $d$ and the smallest spectral scale $\eta$ for which Theorem 1.1 applies, the parameter $\xi$ needs to be chosen as small as permitted, which is slightly smaller than $(\log N)^{2}$. In particular, the local semicircle law holds for all $\eta\geqslant(\log N)^{4}/N$ and all $d\geqslant(\log N)^{4}$ satisfying $d\leqslant N^{2/3}(\log N)^{-4/3}$ for the uniform model and $d\leqslant N^{2}(\log N)^{-4}$ for the permutation and matching models.

For instance, Theorem 1.1 implies that all eigenvectors are completely delocalized.

which follows easily from (1.9). Thus $v_{\alpha,i}^{2}\leqslant 2\eta=O(\xi^{2}/N)$ as claimed, concluding the proof. ∎

Next, Theorem 1.1 yields a semicircle law on small scales for the empirical spectral measure of $H$. The Stieltjes transform of the empirical spectral measure of $H$ is defined by

where $\lambda_{1},\dots,\lambda_{N}$ are the eigenvalues of $H$. Theorem 1.1 implies that

denote the semicircle and empirical spectral measures, respectively, applied to an interval $I$. Fix a constant $K>0$. Then, under the assumptions of Theorem 1.1, for any interval $I\subset[-K,K]$ we have

Corollary 1.3 says in particular that, in the bulk spectrum, the empirical spectral density of $H$ is well approximated by the semicircle law down to spectral scales $\xi^{2}/N$. Indeed, fix $\varepsilon>0$ and suppose that $I\subset[-2+\varepsilon,2-\varepsilon]$, so that $\kappa(I)\geqslant\varepsilon$. Then the right-hand side of (1.18) is much smaller than $\varrho(I)$ provided that $\lvert I\rvert\gg\xi^{2}/N$. We deduce that the distribution of the eigenvalues of $H$ is very regular all the way down to the microscopic scale. Moreover, clumps of eigenvalues containing more than $(\log N)^{4}$ eigenvalues are ruled out with high probability: any interval of length at most $(\log N)^{4}/N$ contains with high probability at most $O((\log N)^{4})$ eigenvalues.

The estimate (1.18) deteriorates near the edges, when $\kappa(I)$ is small. Here we do not aim for an optimal edge behaviour, and (1.18) can in fact be improved near the edges by a more refined application of (1.17). For example, from (1.17) we also obtain the estimate

Up to the logarithmic correction $\xi$, we expect that the estimates (1.12) cannot be improved in the bulk of the support of the semicircle law, i.e. for $|E|\leqslant 2-\varepsilon$. On the other hand, (1.12) is not optimal for $|E|\geqslant 2-\varepsilon$. For example, a simple extension of our proof allows one to show that the term $\xi\Phi(z)$ on the right-hand sides of (1.12) can be replaced by the smaller bound

In order to focus on the main ideas of this paper, we give the proof of the simpler estimate (1.12). In Appendix A, we sketch the required changes to obtain the improved error bound (1.20). The bound (1.12) is sufficient for most applications, including Corollaries 1.2–1.3. Finally, we remark that all of our error bounds are designed with the regime of bounded $z$ in mind; as $z\to\infty$, much better bounds can be easily obtained. We do not pursue this direction here.

4. Related results

We conclude this section with a discussion of some related results. The convergence of the empirical spectral measure of a random $d$-regular graph has been previously established on spectral scales slightly smaller than the macroscopic scale $1$. More precisely, in (MR2999215, , Theorem 1.6), the semicircle law is established down to the spectral scale $d^{-1/10}$ for $d\to\infty$. In (MR3025715, , Theorem 2 and Remark 1), the semicircle law is established down to the spectral scale $(\log N)^{-1}$ for $d=(\log N)^{\gamma}$ with $\gamma>1$, and the spectral scale $1/d$ for $d=(\log N)^{\gamma}$ with $\gamma<1$. In (1304.4343, , Theorem 5.1), it is shown that for fixed $d$ the Kesten-McKay law holds down to the spectral scale $(\log N)^{-c}$ for some $c>0$. Finally, in (1305.1039, , Theorem 2.1), it is shown that for fixed $d$ the Kesten-McKay law holds down to the spectral scale $(\log N)^{-1}$.

The results of MR2999215 were proved by coupling to an Erdős-Rényi graph. The probability that an Erdős-Rényi graph in which each edge is chosen independently with probability $p$ is $d$-regular, with $d=pN$, is at least $\exp(-cN\log d)$. Hence, any statement that holds for the Erdős-Rényi graph with probability greater than $1-\exp(-cN\log d)$ also holds for the random $d$-regular graph. While global spectral properties can be established with such high probabilities, super-exponential error probabilities are not expected to hold for local spectral properties.

In a related direction, contiguity results imply that almost sure asymptotic properties of various models of random regular graphs can be related to each other (see e.g. MR1725006 for details). Such results are difficult to extend to the case where $d$ grows with $N$, for example because the probability that a graph of the permutation model is simple tends to zero roughly like $\exp(-cd^{2})$. This probability is smaller than the error probabilities that we establish in this paper. Our proof does not rely on a comparison between different models, but works directly with each model. It is rather general, and may in particular be adapted to other models of random regular graphs. For instance, by an argument similar to (but somewhat simpler than) the one given in Section 6, we may prove Theorem 1.1 for the configuration model of random regular graphs. Moreover, by a straightforward extension of our method, our results remain valid for arbitrary superpositions of the models from Section 1.2. For example, we can consider a regular graph defined as the union of several independent uniform regular graphs of lower degree. (In fact, the matching model is the union of $d$ independent copies of a uniform $1$-regular graph).

Our proof does not use the tree approximation. Instead, we use that a local resampling using appropriately chosen switchings leaves the random regular graphs from Section 1.2 invariant. Switchings of random regular graphs were introduced to prove enumeration results in MR790916 ; see also MR1725006 for a survey of subsequent developments. Switchings are also commonly used for simulating random regular graphs using Monte Carlo methods; see e.g. MR2334585 and references therein. Recently, switchings were employed to bound the singularity probability of directed random regular graphs 1411.0243 .

For $d$-regular graphs, the value of second largest eigenvalue $\lambda_{2}$ is of particular interest. At least for fixed $d\geqslant 3$, it was conjectured that for almost all random $d$-regular graphs we have $\lambda_{2}=2\sqrt{d-1}+o(1)$ with high probability MR875835 . For fixed $d$, this conjecture was proved in MR2437174 , following several larger bounds (for which references are given in MR2437174 ). Very recently, the results ofMR2437174 were generalized and their proofs simplified in MR3385636 ; Bord15 . For the permutation model with $d\to\infty$ as $N\to\infty$, the best known bound is $\lambda_{2}=O(\sqrt{d})$ FriedmanKahnSzemeredi (see (MR3078290, , Theorem 2.4) for a more detailed proof).

Finally, it is believed that the eigenvalues of random $d$-regular graphs obey random matrix statistics as soon as $d\geqslant 3$. There is numerical evidence that the local spectral statistics in the bulk of the spectrum are governed by those of the Gaussian Orthogonal Ensemble (GOE) MR2647344 ; MR1691538 , and further that the distribution of the appropriately rescaled second largest eigenvalue $\lambda_{2}$ converges to the Tracy-Widom distribution of the GOE MR2433888 .

In 1505.06700-aop , with J. Huang, we prove that GOE eigenvalue statistics hold in the bulk for the uniform random $d$-regular graph with degree $d\in[N^{\alpha},N^{2/3-\alpha}]$ for arbitrary $\alpha>0$. Here, the lower bound on the degree is of purely technical nature, and we believe that the results of 1505.06700-aop can be established with the same method under the weaker assumption $d\geqslant(\log N)^{O(1)}$. The local law proved in this paper, in addition to the results of 1504.03605 ; 1504.05170 , is an essential input for the proof in 1505.06700-aop .

For Erdős-Rényi graphs, in which each edge is chosen independently with probability $p$, the local semicircle was established under the condition $pN\geqslant(\log N)^{O(1)}$ in MR3098073 . Moreover, random matrix statistics for both the bulk eigenvalues and the second largest eigenvalue were established in MR2964770 under the condition $pN\geqslant N^{2/3+\alpha}$ for arbitrary $\alpha>0$. For random matrix statistics of the bulk eigenvalues, the lower bound on $pN$ was recently extended to $pN\geqslant N^{\alpha}$ for any $\alpha>0$ in 1504.05170 , and GOE statistics for the eigenvalue gaps was also established. Previous results on the spectral statistics of Erdős-Rényi graphs are discussed in MR2964770 ; MR3098073 ; MR2999215 .

Preliminaries and the self-improving estimate

In this section we introduce some basic tools and definitions on which our proof relies, and state a self-improving estimate, Proposition 2.2, from which Theorem 1.1 will easily follow. The rest of this paper will be devoted to the proof of Proposition 2.2.

From now on we frequently omit the spectral parameter $z$ from our notation, and write $G\equiv G(z)$ and so on. The spectral representation of $G$ implies the trivial bound

We shall also use the resolvent identity: for invertible matrices $A,B$,

In particular, applying (2.2) to $G-G^{*}$, we obtain the Ward identity

The core of the proof is an induction on the spectral scale, where information about $G$ is passed on from the scale $\eta$ to the scale $\eta/2$. (See Remark 2.3 below for a comparison of this induction with the bootstrapping/continuity arguments used in the proofs of local laws in models with independent entries.) The next lemma is a simple deterministic result that allows us to propagate bounds on the Green’s function on a certain scale to weaker bounds on a smaller scale. This result will play a crucial role in the induction step. In order to state it, we introduce the random error parameters

Thus, $\Gamma$ is locally Lipschitz continuous, and its almost everywhere defined derivative satisfies

This implies $\frac{\partial}{\partial\eta}(\eta\Gamma(\eta))\geqslant 0$ and therefore $\Gamma(\eta/M)\leqslant M\Gamma(\eta)$ as claimed. ∎

The main ingredient of the proof of Theorem 1.1 is the following result, whose proof constitutes the remainder of the paper. To state it, we introduce the set

where the implicit absolute constant in $\ll$ is chosen large enough in the proof of the following result.

Given Proposition 2.2, Theorem 1.1 is a simple consequence.

for $k\in[\![{0,K}]\!]$. The claim (2.7) is trivial for $k=0$ since then $\eta_{k}=N$ and therefore (2.1) implies $\Gamma^{*}(z_{k})\leqslant 1$ deterministically. Now assume that (2.7) holds for some $k\in[\![{0,K}]\!]$. Then Lemma 2.1 applied with $\eta=\eta_{k}$ and $M=2$ implies

The induction in the proof of Theorem 1.1 is not a continuity (or bootstrapping) argument, as used e.g. in the works MR3068390 ; MR3098073 ; MR2481753 on local laws of models with independent entries. The multiplicative steps $\eta\to\eta/2$ that we make are far too large for a continuity argument to work, and we correspondingly obtain much weaker a priori estimates from the induction hypothesis. Thus, our proof relies on a priori control of $\Gamma$ instead of the error parameters $\Lambda_{d}$ and $\Lambda_{o}$ used in MR3068390 ; MR3098073 ; MR2481753 . The advantage, on the other hand, of the approach taken here is that we only have to perform an order $\log N$ steps, as opposed to the $N^{C}$ steps required in bootstrapping arguments. As evidenced by the proof of Theorem 1.1, a logarithmic bound on the number of induction steps is crucial. An inductive approach was also taken in 1311.0326 , where a local semicircle law without logarithmic corrections was proved for Wigner matrices with entries whose distributions are subgaussian.

It therefore only remains to prove Proposition 2.2. This is the subject of the remainder of the paper, which we now briefly outline. We follow the concentration/expectation approach, establishing concentration results on the entries of $G$ (Section 4) and computing the expectation of the diagonal entries (Section 5). All of this is performed with respect to a conditional probability measure, which is constructed for each fixed vertex. Roughly speaking, given a vertex, this conditional probability measure randomizes the neighbours of the vertex in an approximately uniform fashion. It is model-dependent and has to be chosen with great care for all of the concentration/expectation arguments of Sections 4–5 to work. Its construction is easiest for the matching model, which we explain in Section 3. The constructions for the uniform and permutation models are given in Sections 6 and 7 respectively.

Local resampling

All models of random regular graphs that we consider are invariant under permutation of vertices. However, for our analysis, it is important to use a parametrization that distinguishes a fixed vertex. Without loss of generality, we assume this vertex to be $1$. This parametrization has to satisfy a series of properties, which are given in Proposition 3.7 below. Using these properties, in Sections 4–5, we complete the proof of Proposition 2.2. Loosely speaking, the parametrization allows us to resample the neighbours of $1$, independently, and only changing a fixed number of edges in the remainder of the graph in a sufficiently random way. In this section, we describe the parametrization and prove Proposition 3.7 for the matching model. The parametrizations for the uniform and permutation models are discussed in Section 6 and 7 respectively.

Random indices will play an important role throughout the paper. We consistently use the letters $i,j,k,l,m,n$ to denote deterministic indices, and $x,y$ to denote random indices.

Our basic strategy of local resampling involves randomizing the neighbours of the fixed vertex $1$ by local changes of the graph, called switchings in the graph theory literature MR1725006 . We use double switchings which involve three edges, as opposed to single switchings which only involve two edges. Both are illustrated in Figure 3.1.

Let $\Delta_{ij}$ denote the adjacency matrix of a graph containing only an edge between the vertices $i$ and $j$,

To define switchings of a set of unoriented edges, it is convenient to assign directions to the edges to be switched. These directions determine which one of the possible switchings of the unoriented edges is chosen. We define the single switching of two edges $r\underline{r},a\underline{a}$ of $A$ with the indicated directions to be the graph

if $\lvert\{{r,\underline{r},a,\underline{a}}\}\rvert=4$, and the graph $\tau_{r\underline{r}\!\,,a\underline{a}\!\,}(A)\mathrel{\vbox{\hbox{.}\hbox{.}}}=A$ if $\lvert\{{r,\underline{r},a,\underline{a}}\}\rvert<4$. The double switching of the three edges $r\underline{r},a\underline{a},b\underline{b}$ of $A$ with the indicated directions is defined to be the graph

if $\lvert\{{r,\underline{r},a,\underline{a},b,\underline{b}}\}\rvert=6$, and the graph $\tau_{r\underline{r}\!\,,a\underline{a}\!\,,b\underline{b}\!\,}(A)\mathrel{\vbox{\hbox{.}\hbox{.}}}=A$ if $\lvert\{{r,\underline{r},a,\underline{a},b,\underline{b}}\}\rvert<6$.

Our goal is to use switchings to connect the distinguished vertex $1$ to essentially independent random vertices $a_{1},\dots,a_{d}$ that are approximately uniform in the sense of the next definition.

To give an idea how approximately uniform random variables arise, consider a switching with $\underline{r}=1$ (to achieve our goal of connecting $1$ to a given vertex $a$ using a switching). For simple graphs, a necessary condition to apply the switching (3.3) is $a\neq 1$. Choosing $a$ uniformly with this constraint means that it is uniform on $[\![{2,N}]\!]$. In particular, the total variation distance of its distribution to that of the uniform distribution is O\bigl{(}{\frac{1}{N}}\bigr{)}=O\bigl{(}{\frac{1}{\sqrt{dD}}}\bigr{)}.

Throughout this paper, $\frac{1}{\sqrt{dD}}$ appears frequently as a bound on exceptional probabilities, and we tacitly use the estimates

which follow directly from (1.5)–(1.6), as well as

We use the following conventions for conditional statements.

The use of double switchings opposed to single switchings ensures that either condition (a) or (b) in the next lemma holds. These conditions will play an important role in Section 5. (That double switchings are in general more effective than single switchings is well known in the combinatorial context; see for instance MR1725006 for a discussion.)

where $X$ is a sum of at most 8 terms $\pm\Delta_{xy}$. Explicitly, in the case

We emphasize that when we say that $x$ and $y$ are approximately uniform, this is a statement about their individual distributions, and as such implies nothing about their joint distribution.

The introduction of switchings that connect $1$ to essentially independent random vertices $a_{1},\dots,a_{d}$ is simplest in the matching model, in which the different neighbours of any given vertex are independent, so that it suffices to consider a single neighbour of $1$ at a time. In the next subsection, we explain in detail how this parametrization using switchings is defined for the matching model.

We state the conclusion, Proposition 3.7, in great enough generality that it holds literally also for all of the other models, for which the more involved proofs are given in Sections 6–7. In the proof of Proposition 2.2 (given in Sections 4–5), and therefore in the proof of Theorem 1.1, we only use the conclusion contained in Proposition 3.7, and no other properties of the model. Hence, Proposition 3.7 summarizes everything about the random regular graphs that our proof requires.

2. Matching model

The matching model was defined in Section 1.2 in terms of $d$ independent uniform perfect matchings of $[\![{1,N}]\!]$. We first consider one such uniform perfect matching, i.e. a uniform $1$-regular graph. We denote by $S_{N}$ the symmetric group of order $N$. For $N$ even, denote by $M_{N}\subset S_{N}$ the set of perfect matchings of $[\![{1,N}]\!]$, which (as explained in Section 1.2) we identify with the subset of permutations whose cycles all have length $2$; in particular $\pi=\pi^{-1}$ for $\pi\in M_{N}$. For any perfect matching $\sigma\in M_{N}$, we denote the corresponding symmetric permutation matrix by

Next, for $i,j,k\in[\![{1,N}]\!]$, we define the switching operation $T_{ijk}\mathrel{\vbox{\hbox{.}\hbox{.}}}M_{N}\to M_{N}$ through

where we recall that $\tau$ was defined in (3.3). In particular, $T_{ijk}$ connects $i$ to $j$ (see Figure 3.1) except in the exceptional case $|\{i,j,k,\pi(i),\pi(j),\pi(k)\}|<6$.

Let $\pi$ be uniform over $M_{N}$, $i\in[\![{1,N}]\!]$ fixed, and $a,b$ independent and uniform over $[\![{1,N}]\!]\setminus\{i\}$. Then $T_{iab}(\pi)$ is uniform over $M_{N}$, and

provided that $|\{i,a,b,\pi(i),\pi(a),\pi(b)\}|=6$.

To prove that $T_{iab}(\pi)$ is uniform over $M_{N}$, it suffices to check reversibility, i.e. that, for any fixed $\sigma,\sigma^{\prime}\in M_{N}$,

Given $\sigma,\sigma^{\prime}\in M_{N}$, $\sigma\neq\sigma^{\prime}$, there is at most one pair $(a,b)\in([\![{1,N}]\!]\setminus\{i\})^{2}$ such that $T_{iab}(\sigma)=\sigma^{\prime}$, and such a pair exists if and only if there exists a (different) pair $(a,b)$ such that $T_{iab}(\sigma^{\prime})=\sigma$ (see Figure 3.1 (right) for an illustration). If no such pairs exist, both sides of (3.11) are zero. Otherwise, there exists precisely one pair $(a,b)$ such that $T_{iab}(\sigma)=\sigma^{\prime}$, so that the left-hand side of (3.11) is equal to $1/(N-1)^{2}$ because $(a,b)$ is uniformly distributed over $(N-1)^{2}$ elements; the same argument shows that the right-hand side of (3.11) is also equal to $1/(N-1)^{2}$, which concludes the proof of (3.12). Finally, (3.11) is immediate from the definition of $T_{iab}$. ∎

The canonical realization of the probability space of the matching model is the product of $d$ copies of the uniform measure on $M_{N}$. For our analysis, we instead employ the larger probability space $\Omega\mathrel{\vbox{\hbox{.}\hbox{.}}}=\Omega_{1}\times\cdots\times\Omega_{d}$ where

also endowed with the uniform probability measure. Elements of $\Omega_{\mu}$ are written as $(\pi_{\mu},a_{\mu},b_{\mu})$. We set $\theta=(\pi_{1},\dots,\pi_{d})$, $u_{\mu}=(a_{\mu},b_{\mu})$, and

By Lemma 3.4, $\sigma_{1},\dots,\sigma_{d}$ are independent uniform perfect matchings of $[\![{1,N}]\!]$, and therefore the matching model is given by the adjacency matrix

Throughout the following, we say that $(\alpha_{1},\dots,\alpha_{d})\in[\![{1,N}]\!]^{d}$ is an enumeration of the neighbours of $1$ if

(Recall that, as explained in the beginning of Section 3, the vertex $1$ is distinguished.) Defining $\alpha_{\mu}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\sigma_{\mu}(1)$, we find that $(\alpha_{1},\dots,\alpha_{d})$ is an enumeration of the neighbours of $1$.

3. General parametrization

Having described the probability space and the parametrization of the neighbours of $1$ for the matching model, we now generalize this setup in order to admit other models of random regular graphs as well.

whose points we denote by $(\theta,u_{1},\dots,u_{d})$. Conditioned on $\theta\in\Theta$, the variables $u_{1},\dots,u_{d}$ are independent. For $\mu\in[\![{1,d}]\!]$ we define $\sigma$-algebras

We also define ${\mathcal{F}}_{0}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\sigma(\theta)$.

In general, as in the case of the matching model in Section 3.2, the variable $u_{\mu}$ for $\mu\in[\![{1,d}]\!]$ determines (with high probability given $\theta\in\Theta$) the $\mu$-th neighbour of $1$. Note that we have introduced an artificial ordering of the neighbours of $1$; this ordering will prove convenient in Sections 4–5. The interpretation of the $\sigma$-algebras (3.18)–(3.19) is that ${\mathcal{G}}_{\mu}$ determines all neighbours of $1$ except the $\mu$-th one, and ${\mathcal{F}}_{\mu}$ determines the first $\mu$ neighbours of $1$.

Having constructed the probability space $\Omega$, we augment it with independent copies of the random variables $u_{1},\dots,u_{d}$.

Remark 3.3 and Lemma 3.4 imply the following key result for the matching model, which is the main result of this section. We state it in a sufficiently general form that holds for all graph models simultaneously; the proof for the other models is given in Sections 6–7. For the matching model, the parametrization in its statement and the corresponding random variables from (3.22) were defined explicitly in Section 3.2: $a_{i}$ below (3.13), $\alpha_{i}$ below (3.16), and $A$ in (3.15).

For any model of random $d$-regular graphs introduced in Section 1.2, there exists a parametrization satisfying Definition 3.5, augmented according to Definition 3.6, with ${\mathcal{F}}_{d}$-measurable random variables

$A$ is the adjacency matrix of the $d$-regular random graph model under consideration, and $(\alpha_{1},\dots,\alpha_{d})$ is an enumeration of the neighbours of $1$ in the sense of (3.16).

(Neighbours of 1.) Fix $\mu\in[\![{1,d}]\!]$.

Conditioned on ${\mathcal{G}}_{\mu}$, the random variable $a_{\mu}$ is approximately uniform.

Conditioned on ${\mathcal{F}}_{0}$, with probability 1-O\bigl{(}{\frac{1}{\sqrt{dD}}}\bigr{)} we have $\alpha_{\mu}=a_{\mu}$.

(Behaviour under resampling.) Fix $\mu\in[\![{1,d}]\!]$.

Conditioned on $\mathcal{F}_{0}$, with probability 1-O\bigl{(}{\frac{1}{\sqrt{dD}}}\bigr{)} we have

The parametrization obeying Definition 3.5 and the random variables (3.22) for the matching model were defined in Section 3.2. We augment the probability space according to Definition 3.6.

First, we prove (ii). By definition, the random variable $a_{\mu}$ is uniform on $[\![{2,N}]\!]$ and hence approximately uniform on $[\![{1,N}]\!]$, showing (ii)(1). By (3.11), $\alpha_{\mu}=\sigma_{\mu}(1)=a_{\mu}$ holds on the event $|\{1,\pi(1),a,\pi(a),b,\pi(b)\}|=6$. The latter event has probability $1-O(\frac{1}{N})\geqslant 1-O(\frac{1}{\sqrt{dD}})$ conditioned on ${\mathcal{G}}_{\mu}$, and hence in particular conditioned on ${\mathcal{F}}_{0}$, which proves (ii)(2).

Next, we prove (iii). By the definitions (3.14)–(3.15),

To show the second claim of (iii)(1) and to show (iii)(2), we may assume that

since this event occurs with probability at least 1-O\bigl{(}{\frac{1}{N}}\bigr{)}\geqslant 1-O(\frac{1}{\sqrt{dD}}) conditioned on $\mathcal{G}_{\mu}$ (and hence also conditioned on $\mathcal{F}_{0}$). Under (3.24), we get

4. Stability of the Green’s function under resampling

From now on we make use of the following notations for conditional expectations and conditional $L^{p}$-norms.

In particular, $\|X\|_{L^{p}({\mathcal{G}})}$ is a ${\mathcal{G}}$-measurable random variable, and

Moreover, for any $\mathcal{F}_{d}$-measurable random variable $X\equiv X(\theta,u_{1},\dots,u_{d})$ we have

The following result is an important consequence of Proposition 3.7 for the Green’s function. It relies on the fundamental random control parameter

In particular, $\Gamma_{\mu}=\Gamma+O(d^{-1/2}\Gamma_{\mu}\Gamma)$, and therefore $\Gamma\ll\sqrt{d}$ implies $\Gamma_{\mu}\leqslant 2\Gamma$.

For random variables $x,y$ such that, conditioned on ${\mathcal{G}}_{\mu}$ and $x$, the random variable $y$ is approximately uniform,

Assuming that $\Gamma=O(1)$, Lemma 3.9 (i) states that the Green’s function has a bounded differences property with respect to the $u_{\mu}$: it only changes by the small amount $O(d^{-1/2})=O(\Phi)$ if a single $u_{\mu}$ is changed. Lemma 3.9 (ii) states that if one of its indices is random, then (conditioned on $\mathcal{G}_{\mu}$) the $L^{2}$-norm of the Green’s function is smaller (again by a factor $\Phi$) than its $L^{\infty}$-norm.

We start with (i). The resolvent identity (2.2) implies

Since, conditioned on $\hat{{\mathcal{G}}}_{\mu}$ and $x$, the distribution of $y$ has total variation distance O\bigl{(}{\frac{1}{\sqrt{dD}}}\bigr{)}\leqslant O\bigl{(}{\frac{1}{D}}\bigr{)} to the uniform distribution on $[\![{1,N}]\!]$, and since $|\hat{G}_{xy}|^{2}\leqslant\Gamma_{\mu}^{2}\leqslant\Gamma_{\mu}^{4}$, the Ward identity (2.3) implies

Finally, by (3.27), $\operatorname{Im}\hat{G}_{xx}\leqslant\Gamma_{\mu}+O(D^{-1/2}\Gamma_{\mu}^{2})$, and therefore

Concentration

The rest of this section is devoted to the proof of Proposition 4.1. The main tool in its proof is the following general concentration result.

Let $X$ be a complex-valued ${\mathcal{F}}_{d}$-measurable random variable, and $Y_{1},\dots,Y_{d}$ nonnegative random variables such that $Y_{\mu}$ is ${\mathcal{G}}_{\mu}$-measurable. Let $N$ satisfy $d\leqslant N^{O(1)}$. Suppose that for all $\mu\in[\![{1,d}]\!]$ we have

with probability at least $1-e^{-(\xi\log\xi)\wedge\zeta+O(\log N)}$.

To prove Proposition 4.2, we define the complex-valued martingale

Let $({\mathcal{F}}_{\mu})_{\mu=0}^{d}$ be a filtration of $\sigma$-algebras and $(X_{\mu})_{\mu=0}^{d}$ be a complex-valued $({\mathcal{F}}_{\mu})$-martingale. Suppose that there are deterministic constants $M,s_{0},s_{1},\dots,s_{d-1}>0$ such that

where $S\mathrel{\vbox{\hbox{.}\hbox{.}}}=\sum_{\mu=0}^{d-1}s_{\mu}$.

it suffices to prove that any real-valued martingale $X$ satisfying (4.5) obeys

Hence, from now on, we assume that $X$ is real-valued.

The estimate (4.7) then follows by the exponential Chebyshev inequality with the choice \lambda\mathrel{\vbox{\hbox{.}\hbox{.}}}=\frac{1}{M}\operatorname{arcsinh}\bigl{(}{\frac{M\xi}{2S}}\bigr{)}, and an application of the same estimate with $X$ replaced by $-X$. ∎

and if the above set is empty we set $\tau\mathrel{\vbox{\hbox{.}\hbox{.}}}=d$. By definition, $\tau$ is an $({\mathcal{F}}_{\mu})$-stopping time. The following result shows that $\tau<d$ on an event of low probability.

Since $\tau$ is an $({\mathcal{F}}_{\mu})$-stopping time, $X_{\mu}^{\tau}\mathrel{\vbox{\hbox{.}\hbox{.}}}=X_{\mu\wedge\tau}$ is an $({\mathcal{F}}_{\mu})$-martingale. Because of Lemma 4.4 and using a union bound, it will be sufficient to study $X^{\tau}_{\mu}$ instead of $X_{\mu}$. The next result shows that $X_{\mu}^{\tau}$ satisfies the assumptions of Lemma 4.3.

Note that, by definition, $\phi_{\mu}=1$ implies that $\|Y_{\mu+1}\|_{L^{2}({\mathcal{F}}_{\mu})}\leqslant 2\gamma=O(1)$, and that, by independence,

We now prove (4.9). By the first bound of (4.2),

By Lemmas 4.3–4.5, and $\xi\operatorname{arcsinh}\xi=\xi\log 2\xi+O(1)$ for $\xi>0$, we get

2. Proof of Proposition 4.1

The following result is the main ingredient in the verification of the second bound of (4.2). For its statement, we recall the definition of $\Gamma_{\mu}$ from (3.26).

Let $\chi$ be the indicator function of the event of $\mathcal{G}_{\mu}$-probability at least 1-O\bigl{(}{\frac{1}{\sqrt{dD}}}\bigr{)} from Proposition 3.7 (iii)(1), and set $\bar{\chi}=1-\chi$. Then the right-hand side of (4.14) is bounded by

We focus first on the second term of (4.15). By Proposition 3.7 (iii)(1) and (4.16),

We first complete the proof for $p=1$. Let $X\mathrel{\vbox{\hbox{.}\hbox{.}}}=\Phi^{-1}G_{ij}$. Then, by (3.27) and $\Phi^{-1}\leqslant d^{1/2}$,

assuming that the constant $C_{p}$ was chosen sufficiently large. This establishes the first estimate of (4.2). The second estimate of (4.2) follows from Lemma 4.6. Therefore Proposition 4.1 follows from Proposition 4.2.

which is bounded by $d^{-1}Y_{\mu}^{2}$ (after choosing $C_{p}$ large enough). The claim now follows from Proposition 4.2. ∎

Expectation

In this section we prove Proposition 2.2. We use the spectral parameters

Fix $z_{0}$ as in (5.1). To prove Proposition 2.2, we assume that $D\gg\xi^{2}$ and that

The proof of (5.3)–(5.4) proceeds in the following steps:

Estimate of $s-m$, where $s$ is the Stieltjes transform (1.16) of the empirical spectral measure, and $m$ the Stieltjes transform (1.9) of the semicircle law.

Step (i) represents most of the work. Throughout this section we make the assumption (5.2).

For the proof of Proposition 2.2 we use the following convenient notion of high probability.

From now on, these properties will be used tacitly.

Furthermore, from now on, the parameter $t$ in Definition 5.1 will always be

with $\zeta$ and $\xi$ the parameters given in the assumption of Proposition 2.2. Then, for any $z$ as in (5.1), we get from the assumption (5.2) and Proposition 4.1 that, with $t$-HP, for all deterministic $i,j,k,l,m,n\in[\![{1,N}]\!]$,

To prove Proposition 2.2, we need to show that (5.3)–(5.4) then also hold with $t$-HP.

2. Derivation of self-consistent equation

In this subsection we derive the self-consistent equation, (5.35) below, which will allow us to obtain estimates on the entries of $G$ and hence prove Proposition 2.2. The following lemma is, in combination with the concentration bounds (5.7)–(5.8), the main estimate in its derivation. For its statement, recall from Proposition 3.7 that $(\alpha_{1},\dots,\alpha_{d})$ is an enumeration of the neighbours of $1$. For the following we introduce the abbreviation

The following lemma provides several elementary bounds on the Green’s function. It is the main computational tool in the proof of Lemma 5.2.

For all $i,j,k,l,m,n\in[\![{1,N}]\!]$ we have

For any $i,j,k,l,m,n\in[\![{1,N}]\!]$ we have

(ii) We show (5.17); the proofs of (5.16) and (5.18) are analogous. Since $\chi\leqslant 1$,

(iv) We show (5.21); the proof of (5.22) is analogous. Under assumption (a), the Cauchy-Schwarz inequality and (3.28) imply

with $t$-HP, where we again used (5.5). This completes the proof. ∎

with $t$-HP. Similarly, by (5.17), (5.19), and (5.15), we get

with $t$-HP. From (5.30)–(5.2), we conclude that

The main idea of the proof of Lemma 5.2 is (5.30): the left-hand side is a difference of Green’s functions with different indices, while the right-hand side is (up to a small error) a difference of Green’s functions with the same indices but the first Green’s function is computed in terms of a switched graph.

We now have all of the ingredients to derive the self-consistent equation for the diagonal entries of $G$.

The event that (5.35) holds is measurable with respect to $A$. By invariance of the law of $A$ under permutation of vertices, and a union bound, it therefore suffices to establish (5.35) for $j=1$ only. Then (5.36) follows by averaging (5.35) over $j$.

To show (5.37), we use that by $(H-z)G=I$ and (1.7), with (5.9),

with $t$-HP. This implies (5.37) and therefore completes the proof. ∎

Under the assumptions of Proposition 2.2, the statement of Lemma 5.4 may be strengthened as follows.

Let $z_{0}$ be as in (5.1) and suppose that (5.2) holds. Then with $t$-HP the estimates (5.35)–(5.36) hold simultaneously for all $z$ as in (5.1).

3. Stability of the self-consistent equation

In Lemma 5.5 we showed that, with $t$-HP,

To show that $m$ and $s$ are close, we use the stability of the equation (5.42), in the form provided by the following deterministic lemma. The stability of the solutions of the equation (5.42) is a standard tool in the proofs of local semicircle laws for Wigner matrices; see e.g. MR2481753 . Our version given below has weaker assumptions than previously used stability estimates; in particular, we do not (and cannot) assume an upper bound on the spectral parameter $E$.

Denote by $m$ and $\hat{m}$ the two solutions of (5.42) with positive and negative imaginary parts, respectively:

where the square root is chosen so that $\operatorname{Im}m>0$. Hence, $\operatorname{Im}\sqrt{z^{2}-4}>\eta$ and consequently $\operatorname{Im}\hat{m}<-\eta$; we shall use this bound below. Note that $m$ and $\hat{m}$ are continuous. Set $v\mathrel{\vbox{\hbox{.}\hbox{.}}}=s-m$ and $\hat{v}\mathrel{\vbox{\hbox{.}\hbox{.}}}=s-\hat{m}$. Since

In the last inequality, we used that $\lvert R\rvert\leqslant(1+|z|)r$ and that, for any $r\in$,

The proof is divided into three cases. First, consider the case $(1+|z|)r(\eta)\geqslant|z^{2}-4|/16$. Then, using (5.49) and the fact that $\lvert\hat{v}-v\rvert=\sqrt{\lvert z^{2}-4\rvert}$, we get

and hence $|v|\leqslant|v|\wedge|\hat{v}|+O(F(r))=O(F(r))$ by (5.48).

Next, consider the case $\eta\geqslant 3$. Then, on the one hand, by (5.48) and the assumption $r\in$, we have $|v|\wedge|\hat{v}|\leqslant 3F(r)\leqslant 3$. On the other hand, since $\operatorname{Im}s>0$ and $\operatorname{Im}\hat{m}<-\eta\leqslant-3$,

and together we conclude that $|\hat{v}|>|v|$, so that the claim follows from (5.48).

Finally, consider the case $(1+|z|)r(\eta)<|z^{2}-4|/16$ and $\eta<3$. Without loss of generality, we set $\eta_{0}=\eta$. Since $r$ is nonincreasing and $|z^{2}-4|$ increasing in $\eta$, and since $(1+|z|)\leqslant 4(1+|z_{0}|)$ for $\eta\in[\eta_{0},3]$, we then have $(1+|z|)r(\eta)<|z^{2}-4|/4$ for all $\eta\in[\eta_{0},3]$. Therefore

On the other hand, by (5.48), and since $|R|\leqslant(1+|z|)r$,

By continuity and (5.52)–(5.53), it suffices to show $|v(z)|<|\hat{v}(z)|$ for some $\eta\in[\eta_{0},3]$, since then $|v(z)|<|\hat{v}(z)|$ for all $\eta\in[\eta_{0},3]$. Since we have already shown $\lvert v(z)\rvert<\lvert\hat{v}(z)\rvert$ for $\eta=3$, the proof is complete. ∎

4. Proof of Proposition 2.2

We now have all the ingredients we need to complete the proof of (5.3)–(5.4) under the assumption (5.2), and hence the proof of Proposition 2.2.

Lemma 5.5 shows that, with $t$-HP, for all $\eta\in[\eta_{0},\eta_{1}]$, the function $s$ satisfies (5.43) with

Having determined $s$, we now estimate $G_{jj}-m$. By (5.35) and since $s=m+O(F(\xi\Phi))$, we find

with $t$-HP. From (1.9) it is easy to deduce that $z+m=-1/m$ and $(1+|z|)|m|=O(1)$. Hence, by (5.55) and since $G_{jj}=O(1)$ with $t$-HP,

The off-diagonal entries of the Green’s function can be estimated using a similar argument.

From $(HG)_{ij}=((H-z)G)_{ij}+zG_{ij}=\delta_{ij}+zG_{ij}$, it follows that

As in (5.38), using (5.58) and (1.7), we find

Using (5.11) we therefore get, with $t$-HP,

Summarizing, we have proved that, assuming (5.2), the estimates (5.3) and (5.4) hold with $t$-HP. Hence the proof of Proposition 2.2 (and consequently of Theorem 1.1) is complete.

This proof of Theorem 1.1 relies on Proposition 3.7, which we proved for the matching model in Section 3.2. In order to establish Theorem 1.1 for the uniform and permutation models, we still have to prove Proposition 3.7 for these models. This is done in Sections 6 and 7, which constitute the rest of the paper.

Uniform model

In this section we prove Proposition 3.7 for the uniform model. We identify a simple graph on the vertices $[\![{1,N}]\!]$ with its set of edges $E$, where an edge $e\in E$ is a subset of $[\![{1,N}]\!]$ with two elements. The adjacency matrix of a set of edges $E$ is by definition

where $\Delta_{ij}$ was defined in (3.1). Note that $M(\cdot)$ is one-to-one, i.e. the matrix $M(E)$ uniquely determines the set of edges $E$. For a subset $S\subset E$ of edges we denote by $[S]\mathrel{\vbox{\hbox{.}\hbox{.}}}=\bigcup_{e\in S}e$ the set of vertices incident to any edge in $S$. Moreover, for a subset $B\subset[\![{1,N}]\!]$ of vertices, we define $E|_{B}\mathrel{\vbox{\hbox{.}\hbox{.}}}=\{{e\in E\mathrel{\vbox{\hbox{.}\hbox{.}}}e\subset B}\}$ to be the subgraph of $E$ induced on $B$.

For a subset $S\subset E$ with $\lvert S\rvert=3$ we define the indicator function

The interpretation of $I(E,S)=1$ is that $S$ is a switchable subset of $E$, i.e. any double switching of the three edges $S$ results again in a simple $d$-regular graph; see Figure 6.1. A switching of the edges $S$ may be identified with a perfect matching of the vertices $[S]$. There are eight perfect matchings $S^{\prime}$ of $[S]$ such that $S\cap S^{\prime}=\emptyset$. We enumerate these matchings in an arbitrary way as $S^{\prime}_{s}$ with $s\in[\![{1,8}]\!]$, and set

and say that $T_{S,s}(E)$ is a switching of $E$. (Compare this with Figure 3.1 (right) in which one such perfect matching is illustrated.) Note that there are $r\underline{r},a\underline{a}\!\,,b\underline{b}\!\,$ depending on $(S,s)$ such that

with the right-hand side defined by (3.3). This correspondence will be made explicit later. The definition (6.2) implies, for $I(E,S)=1$, that $T_{S,s}(E)$ is a simple $d$-regular graph, and that

Next, take two disjoint subsets $S_{1},S_{2}\subset E$ satisfying $I(E,S_{1})=I(E,S_{2})=1$ and $[S_{1}]\cap[S_{2}]=\{{1}\}$. Thus, we require the sets $S_{1}$ and $S_{2}$ to be incident to exactly one common vertex, which we set to be $1$; see Figure 6.2. Then $S_{2}\subset E\setminus S_{1}$ and $S_{1}\subset E\setminus S_{2}$, and (6.4) implies that the two compositions $T_{S_{1},s_{1}}(T_{S_{2},s_{2}}(E))$ and $T_{S_{2},s_{2}}(T_{S_{1},s_{1}}(E))$ are well-defined and coincide,

Let $S$ satisfy $I(E,S)=1$ and $1\in[S]$. The map $T_{S,s}(E)$ switches the unique edge $\{1,i\}\in S$ incident to $1$ to a new edge $\{1,j\}\notin S$ with $j\in[S]$. Our next goal is to extend this switching to a simultaneous switching of all neighbours of $1$. As already seen in (6.5), simultaneous multiple switchings are not always possible, and our construction will in fact only switch those neighbours of $1$ that can be switched without disrupting any other neighbours of $1$. The remaining neighbours will be left unchanged. Ultimately, this construction will be effective because the number of neighbours of $1$ that cannot be switched will be small with high probability.

Let $(e_{1}(E),\dots,e_{d}(E))$ be an enumeration of the edges in $E$ incident to $1$, and denote by

For $\mu\in[\![{1,d}]\!]$ we define the indicator functions

Their interpretation is as follows. On the event $\{I_{\mu}=1\}$, the edges $S_{\mu}$ are switchable in the sense that any switching of them results in a simple $d$-regular graph. The interpretation of $\{J_{\mu}=1\}$ is that the edges of $S_{\mu}$ do not interfere with the edges of any other $S_{\nu}$, and hence any switching of them will not influence or be influenced by the switching of another triple of edges: on the event $\{J_{\mu}=1\}$, (6.5) implies that $T_{S_{\mu},s_{\mu}}$ commutes with $T_{S_{\nu},s_{\nu}}$ for all $\nu\neq\mu$. The set $W$ lists the neighbours of $1$ that can be switched simultaneously; see Figure 6.2.

Let $\mu_{1},\dots,\mu_{k}$, where $k\leqslant d$, be an arbitrary enumeration of $W$, and set

where we used that, by construction of $W$, any switchings $\mu\neq\nu$ with $\mu,\nu\in W$ do not interfere with each other, so that $M(T_{S_{\mu},s_{\mu}}T_{S_{\nu,s_{\nu}}}(E))-M(T_{S_{\nu},s_{\nu}}(E))=M(T_{S_{\mu},s_{\mu}}(E))-M(E)$.

Now we define the bijection $\phi\mathrel{\vbox{\hbox{.}\hbox{.}}}E_{1}\to E_{2}$. For each $\mu\in W$, we choose $\phi$ to be a bijection from $E_{1}|_{B_{\mu}}$ to $E_{2}|_{B_{\mu}}$ such that $\phi(e_{\mu}(E_{1}))$ is incident to $1$. (For each such $\mu$ there are two possible choices for this bijection; this choice is immaterial.) Without loss of generality, we can choose the enumeration $e_{\mu}(E_{2})$ of $E_{2}$ such that $e_{\mu}(E_{2})=\phi(e_{\mu}(E_{1}))$. This defines a bijection $\phi\mathrel{\vbox{\hbox{.}\hbox{.}}}E_{1}\cap E_{\bigtriangleup}\to E_{2}\cap E_{\bigtriangleup}$. We extend it to a bijection $\phi\mathrel{\vbox{\hbox{.}\hbox{.}}}E_{1}\to E_{2}$ by setting $\phi(e)\mathrel{\vbox{\hbox{.}\hbox{.}}}=e$ for $e\in E_{\cap}$.

With these preparations, we now show (6.12). Given $E_{1}$ and $E_{2}$ that are switchings of each other, we have constructed a set $W\subset[\![{1,d}]\!]$ and subsets $B_{\mu}$ for $\mu\in W$, such that $E_{1}|_{B_{\mu}}$ and $E_{2}|_{B_{\mu}}$ are $1$-regular graphs obtained from a unique switching from each other. Since the $s_{\mu}$ are independent and since for each $\mu\in W$ the random variable $s_{\mu}$ is uniform on $[\![{1,8}]\!]$, we find that the left-hand side of (6.12) is equal to

By an identical argument, we find that the right-hand side of (6.12) is equal to

2. Estimate of exceptional configurations

In preparation of the proof of Proposition 3.7 for the uniform model, we now define the probability space $\Omega$ from Definition 3.5. The space $\Theta$ is the set of simple $d$-regular graphs (identified with their sets of edges $E$), and

Hence, the probability space $\Omega=\Theta\times U_{1}\times\cdots\times U_{d}$ from Definition 3.5 consists of elements

From now on, we always condition on $E$ and write $e_{\mu}\equiv e_{\mu}(E)$. We denote by $p_{\mu},q_{\mu}$ the two edges in $S_{\mu}$ not incident to $1$ (ordered in an arbitrary fashion), so that $S_{\mu}=\{e_{\mu},p_{\mu},q_{\mu}\}$. The next lemma provides some general properties of the random sets $S_{\mu}$.

The following holds for any fixed $\mu\in[\![{1,d}]\!]$.

There are at most five $\nu\neq\mu$ such that

We begin with (i). Let $B$ be the set of $\nu\neq\mu$ satisfying (6.17). By definition, for $\nu\in B$, $[S_{\nu}]\cap[S_{\kappa}]=\{{1}\}$ for all $\kappa\neq\mu,\nu$. Thus, each $p\in[S_{\mu}]\setminus\{1\}$ can be contained in at most one $S_{\nu}$ with $\nu\in B$. The claim follows since $[S_{\mu}]\setminus\{1\}$ has at most five elements.

Next, we prove (ii). Conditioned on ${\mathcal{G}}_{\mu}$, the two edges $p_{\mu},q_{\mu}$ are by definition of $S_{\mu}$ chosen to be distinct and uniformly distributed on the $Nd/2-d$ edges not incident to $1$. Let $\partial 1=\{e\in E:1\in e\}$ be the set of edges in $E$ incident to $1$. Then

This shows (6.18); the proof of (6.19) is analogous. ∎

Next, we derive some basic estimates on the indicator functions $I_{\mu}$ and $J_{\mu}$ and the random set $W$. Ideally, we would like to ensure that with high probability $I_{\mu}J_{\mu}=1$. While this event does hold with high probability conditioned on $\mathcal{F}_{0}$, it does not hold with high probability conditioned on $\mathcal{G}_{\mu}$. In fact, conditioned on $\mathcal{G}_{\mu}$, it may happen that $I_{\mu}J_{\mu}=0$ almost surely. This happens if there exists a $\nu\neq\mu$ such that $[S_{\nu}]\cap e_{\mu}\neq\{1\}$. The latter event is clearly independent of $S_{\mu}$. To remedy this issue, we introduce the ${\mathcal{G}}_{\mu}$-measurable indicator function