Sandbox:DavidKohler/Alon try 1/Theorem 4.2

This theorem is a generalization of theorem 2.11 which uses less machinery, mainly because we heavily use covering maps.

Statement

Theorem 4.2
Let H be a graph whose maximal degree is no more than d ≥ 3, then for any d-regular graph G on n vertices which contains the graph H as a subgraph we have the following lower bound on the second largest eigenvalue of the graph G: λ2(G ) ≥ λ1(Treed (H )) − on (1) Where Treed(G) is the d-regular tree completion of the graph H.

Proof

Denote by T the d-regular tree completion of the graph F. Fix an ε > 0, we'll show that λ₂(G ) ≥ λ₁(T) − ε for any d-regular graph G on n vertices as long as n is large enough.

(NOT SO GOOD IN TERMS OF DEFINITIONS HERE) By definition of the largest eigenvalue of an infinite graph, there must exist a function f on the T, the d-regular tree completion of the graph H, with a finite support such that

$\lambda _{1}(T)-\epsilon \leq {\frac {||Bf||}{||f||}}$

Where B is the adjacency operator of the graph T.

(USING TECHNICAL STUFF THAT I DON'T UNDERSTAND YET, some Dirichlet eigenfunctions among other things) WE CAN ASSUME THE FOLLOWING: We can assume that the function f is non-negative and that it satisfies

$Bf\geq (\lambda _{1}(T)-\epsilon )f$

with equality everywhere except on the boundary of the graph H (IS THAT USEFUL?).

Lemma (TO WRITE SEPARATELY)

Let π: H --> G be a covering map and let f be a function on the vertices of the graph H, then the following holds:

$(A_{G}(\pi _{*}f))(v)=\sum _{w\in \pi ^{-1}(v)}(A_{H}f)(w)$

Proof: Just develop the sum, it comes out very naturally.

(BACK TO THE MAIN PROOF)

We claim that the following holds:

$A_{G}(\pi _{*}f)\geq (\lambda _{1}(T)-\epsilon )(\pi _{*}f)$

Indeed, we have that

$(A_{G}(\pi _{*}f))(v)=\sum _{w\in \pi ^{-1}(v)}Bf(w)$

$\geq \sum _{w\in \pi ^{-1}(v)}(\lambda _{1}(T)-\epsilon )f(w)$

$=(\lambda _{1}(T)-\epsilon )\sum _{w\in \pi ^{-1}(v)}f(w)$

$=\left(\lambda _{1}(T)-\epsilon \right)\pi _{*}f(v)$

This allows to estimate the Rayleigh quotient of the function π_*f as follow:

$R_{G}(\pi _{*}f)={\frac {\langle A_{G}(\pi _{*}f),\pi _{*}f\rangle }{\langle \pi _{*}f,\pi _{*}f\rangle }}\geq \lambda _{1}(T)-\epsilon$

by non-negativity of the function f and thus of the function π_*f as well.

Using LEMMA I DON'T KNOW WHERE YET SAYING HOW TO FIND LOWER BOUNDS ON THE SECOND LARGEST EIGENVALUE USING ORTHOGONAL FUNCTIONS, we'll show that we can find an function g which is orthogonal to both functions π_*f and A_G(π_*f) and whose Rayleigh quotient is larger than the Rayleigh quotient of π_*f.

Denote by N the support of the function π_*f and denote by N₁ the set of all vertices at distance at most 1 from the set N (in other words, N₁ is the closed ball centered at the set N of radius 1 in the usual distance metric of the graph). We'll define the function g=1_V \ N1 to be the characteristic function of the complement of the set N₁. By construction, the function g is orthogonal to both functions π_*f and A_G(π_*f) since it takes zero values everywhere those two functions potentially take non-zero values.

Let's estimate the Rayleigh quotient of the function g now. The denominator can be computed precisely:

$\langle g,g\rangle =|V\backslash N_{1}|=n-|V_{1}|$

The numerator can be estimated as follow:

$\langle A_{G}g,g\rangle =\sum _{v\notin N_{1}}(A_{G}g)(v)\geq d(n-d|N_{1}|)$

where the lower bound is obtained by only counting the vertices v at distance at least 2 from the set N₁ for which we'll have (A_Gg )(v )=d since all neighbours of such a vertex v cannot belong to the set N₁. There are at least n − d |N₁| of such vertices which explains the lower bound. We thus obtain the following estimate on the Rayleigh quotient of the function g

$R_{G}(g)={\frac {\langle A_{G}g,g\rangle }{\langle g,g\rangle }}\geq {\frac {d(n-d|N_{1}|)}{n-|N_{1}|}}=d-{\frac {d(d-1)|N_{1}|}{n-|N_{1}|}}$

Note that |N₁| the size of the vertices at distance at most 1 from the support of the function π_*f is of size ... TO DO.