Sandbox:DavidKohler/RAC/Stuff/Theorem 2.11

This theorem indicates that there is a fairly high probability that a random d-regular graph will have a higher eigenvalue than we hope for. This occurs here when a vertex has too many self-loops, a case of what is called a tangle.

Statement

Theorem 2.11
Fix an even integer d ≥ 4 and then fix another integer m such that m < d/2 and 2m-1  > √d - 1. Consider the standard model, Gn,d, of random d-regular graphs on n vertices. Then for sufficiently large n with probability at least n1-m-(1/2)n2-2m we have that λ2(G) > 2√d - 1.

Proof

We're considering the case in which a graph has at least m self-loops, for m < d/2. We'll show that for a value of m large enough relatively to d the second largest eigenvalue will be larger than 2√d - 1 for a sufficiently large value of n.

Throughout this proof, we'll consider the values of d and m fixed while we'll let the value of n grow.

Assume that there are at least m self-loops at the vertex v_k, this is the event, which we'll denote by τ_k, that π_i (v_k) = v_k for i = 1, ..., m. This event occurs with probability 1/n^m since we simply fix the first value of its first m permutations.

Let us denote by τ the probability that there are at least m self-loops at some vertex in the graph, so we have

$\tau =\bigcup _{k=1}^{n}\tau _{k}$

and hence, using the principle of inclusion and exclusion, we can estimate the probability of τ as claimed:

${\text{Prob}}(\tau )\geq \sum _{k=1}^{n}{\text{Prob}}(\tau _{k})-\sum _{k_{1}\neq k_{2}}{\text{Prob}}(\tau _{k_{1}}\cap \tau _{k_{2}})\geq n{\frac {1}{n^{m}}}-{\binom {n}{2}}\left({\frac {1}{n^{m}}}\right)^{2}\geq n^{1-m}-{\frac {1}{2}}n^{2-2m}$

Let us now show how such a graph will give rise to a large second eigenvalue. To do this, we'll use Rayleigh quotients to estimate the second largest eigenvalue as stated HERE.

Let us assume that in a random d-regular graph G we have at least m self-loops at a vertex v₀. Denote by ρ(v) the distance of a vertex v to the vertex v₀ and for any positive integer r consider the function defined on the vertices f_r given by:

$f_{r}(v)={\begin{cases}\left({\frac {1}{2m-1}}\right)^{\rho (v)}&{\text{if }}\rho (v)\leq r\\\quad 0&{\text{otherwise}}\end{cases}}$

We would like to estimate the Rayleigh quotient of the function f_r. For this, we'll consider the function α defined by:

$\alpha (m)=(2m-1)+{\frac {d-1}{2m-1}}$

For which we'll make the following two claims:

1. Under the assumption that 2m-1 > √d - 1 we have that α(m) > 2√d - 1
2. If we denote by A the adjacency matrix of our random graph G then (Af_r)(v ) ≥ α(m)f_r (v ) for any vertex v such that ρ(v ) < r.

The first claim simply follows from Cauchy-Schwarz. The second claim follows from the following. Let v be a vertex such that ρ(v ) < r, then we have that:

$(Af_{r})(v)=\sum _{w\in V_{G}}A_{v,w}f_{r}(w)\geq \left({\frac {1}{2m-1}}\right)^{\rho (v)-1}\!\!\!\!\!\!\!\!+\,\,(d-1)\left({\frac {1}{2m-1}}\right)^{\rho (v)+1}\!\!\!\!\!\!\!\!=\alpha (m)f_{r}(v)$

This estimate comes from the worst case this computation can take when the vertex v has only one vertex closer to the vertex v₀ and the remaining d-1 vertices are further away from the vertex v₀ than the vertex v. The specific case when the vertex v is the vertex v₀ is dealt in a similar way:

$Af_{r}(v_{0})=\sum _{w\in V_{G}}A_{v_{0}w}f_{r}(w)\geq 2mf_{r}(v_{0})+(d-2m){\frac {1}{2m-1}}=\alpha (m)f_{r}(v_{0})$

Here, the worst case is when the vertex v₀ has precisely m self-loops (each contributing twice in the adjacency matrix) and hence d-2m adjacent vertices. Note also that f_r(v₀) = 1.

We can now estimate the Rayleigh quotient of the function f_r. Let us define by <f,g>_r the partial scalar product on vertices at distance at most r:

$\langle f,g\rangle _{r}=\sum _{\begin{array}{c}w\in V_{G}\\\rho (w)\leq r\end{array}}f(w)g(w)$

then we can rewrite our above remarks as follow:

$\displaystyle {\langle f_{r},f_{r}\rangle =\langle f_{r},f_{r}\rangle _{r}}$   and   $\langle Af_{r},f_{r}\rangle \geq \langle Af_{r},f_{r}\rangle _{r}\geq \alpha (m)\langle f_{r},f_{r}\rangle _{r-1}$

This allows to get the following estimate of the Rayleigh quotient of the function f_r:

$R_{A}(f_{r})={\frac {\langle Af_{r},f_{r}\rangle }{\langle f_{r},f_{r}\rangle }}\geq \alpha (m){\frac {\langle f_{r},f_{r}\rangle _{r-1}}{\langle f_{r},f_{r}\rangle _{r}}}$

We know that α(m) is at most 2√d - 1 but the remaining fraction being less than 1, we need to work a little to show that it can be made arbitrarily close to 1 for a suitable value of r. First we can estimate the difference in these two terms as follow: notice that there are at most (d-2m)(d-1)^t-1 vertices at distance t from the vertex v₀ hence:

$\langle f_{r},f_{r}\rangle _{r}\leq \langle f_{r},f_{r}\rangle _{r-1}+(d-2m)(d-1)^{r-1}\left({\frac {1}{2m-1}}\right)^{2r}$

And so

${\frac {\langle f_{r},f_{r}\rangle _{r-1}}{\langle f_{r},f_{r}\rangle _{r}}}\geq 1-{\frac {(d-2m)(d-1)^{r-1}}{\langle f_{r},f_{r}\rangle _{r}(2m-1)^{2r}}}$

Since f_r(v₀) = 1 we have that <f_r,f_r>_t ≥ 1 and hence

${\frac {(d-2m)(d-1)^{r-1}}{\langle f_{r},f_{r}\rangle _{r}(2m-1)^{2r}}}\leq {\frac {d-2m}{d-1}}\left({\frac {d-1}{(2m-1)^{2}}}\right)^{r}$

Which converges to zero if we let r tend to infinity since (d-1)/(2m-1)² < 1. This implies that for any fixed value of m we can choose a value α₀ such that 2√d - 1 < α₀ < α(m) and then choose a value r₀ large enough such that:

${\frac {d-2m}{d-1}}\left({\frac {d-1}{(2m-1)^{2}}}\right)^{r_{0}}<1-{\frac {\alpha _{0}}{\alpha (m)}}$

Which gives the following lower bound on the Rayleigh quotient of the function f_r:

$R_{A}(f_{r})\geq \alpha (m)\left(1-{\frac {d-2m}{d-1}}\left({\frac {d-1}{(2m-1)^{2}}}\right)^{r_{0}}\right)>\alpha _{0}>2{\sqrt {d-1}}$

To complete the proof and use lemma ??? we need to find an orthogonal function with a larger Rayleigh quotient that this.

For simplicity, we'll denote by f the function f_r0 that we obtained above.

Consider the following set of vertices

$N=\left\{w\in V_{G}\,|\,{\text{dist}}_{G}(w,{\text{supp}}(f))\leq 1\right\}$

which contains the support of the function f and all the vertices adjacent to it. We consider now the function g = 1_V\N, which is the characteristic function of the complement set of the set N. By construction, the function f is orthogonal to both g and Ag. We now proceed to estimate the Rayleigh quotient of g. Since <Ag,g> is twice the number of edges in the subgraph induced by the vertices in V\N and since the number of edges in that subgraph is at least (1/2)d|V| - d|N|, that is, the number of edges adjacent to a vertex in the set N subtracted from the total number of edges in the graph; we obtain that:

$R_{A}(g)\geq {\frac {d|V|-2d|N|}{|V|-|N|}}=d-{\textrm {O}}\!\left({\frac {1}{n}}\right)$

Since |V| = n and since we can consider d and |N| to be constants at this point. This implies that for n sufficiently large, we'll have:

$d-{\textrm {O}}\!\left({\frac {1}{n}}\right)\geq \alpha (m)\geq \alpha _{0}$

And hence min{ R_A(f), R_A(g) } = R_A(f) > 2√d - 1; which implies that λ₂(G) > 2√d - 1 and concludes this proof.