Sandbox:DavidKohler/Relativized Alon Conjecture/Trace method

Here, we review the Trace Method.

Basics of the Trace Method

Consider the random regular graph model G_n,d. The trace method allows us to determine information on the eigenvalues of a random regular graph by computing the expected value of the trace of a sufficiently high power of the adjacency matrix. Since the trace of a power of the adjacency matrix is the sum of the corresponding power of its eigenvalues, it passes through expectations and we have

$\displaystyle \mathbb {E} [{\text{Tr}}(A_{G}^{k})]=\lambda _{1}^{k}+\ldots +\lambda _{n}^{k}$

And so

${\begin{aligned}\mathbb {E} [\lambda _{2}]&\leq \left(\mathbb {E} [\lambda _{2}^{k}]\right)^{1/k}\\&\leq \left(\mathbb {E} [\lambda _{1}^{k}+\lambda _{2}^{k}+\ldots +\lambda _{n}^{k}-\lambda _{1}^{k}]\right)^{1/k}\\&\leq \left(\mathbb {E} [{\text{Tr}}(A_{G}^{k})-d^{k}]\right)^{1/k}\\\end{aligned}}$

Since λ₁ = d for d-regular graphs.

The trace of the k^th power of the adjacency matrix of a graph can also be interpreted as the number of closed walks of length k in the graph. In the case of the G_n,d model, each edge is labeled with a letter in the alphabet

$\displaystyle \Pi =\{\pi _{1},\pi _{1}^{-1},\ldots ,\pi _{d/2},\pi _{d/2}^{-1}\}$

where each π_i corresponds to a randomly selected permutation of n objects. Hence a walk of length k corresponds to a word w in this alphabet and hence corresponds to a permutation of n objects (using the usual composition of permutations). And the (i,j) entry of the the k^th power of the adjacency matrix is the number of words w of length k taking i to j. Given a word w, the probability P(w) that the word takes i to itself is clearly independent of i and hence we have

$\displaystyle \mathbb {E} [{\text{Tr}}(A_{G}^{k})]=n\sum _{w\in \Pi ^{k}}P(w)$

Finding ways to estimate the right-hand side of this equation allows to estimate the expected value of the second largest eigenvalue.

In Broder & Shamir

In their paper, Broder and Shamir give an estimate of the right-hand side of the above equation.

To do
	Describe the Broder Shamir approach and main result

In Friedman

In his proof of the regular case of the Alon conjecture, Friedman shows that

ROUGH VERSION

First, P(w) has an expansion in 1/n:

$\displaystyle P(w)=P_{0}(w)+{\frac {P_{1}(w)}{n}}+{\frac {P_{2}(w)}{n^{2}}}+\ldots$

Now set

$\displaystyle g_{i}(k)=\sum _{w\in {\text{Irred}}_{k}}P_{i+1}(w)$

Since P₀(w) = 0 for irreducible words and k at least 1.

And so we can define the Irreducible trace as

$\displaystyle \mathbb {E} [{\text{IrredTr}}(A,k)]=n\sum _{w\in {\text{Irred}}_{k}}P(w)$

and get

$\displaystyle \mathbb {E} [{\text{IrredTr}}(A,k)]=\sum _{i\geq 0}g_{i}(k){\frac {1}{n^{i}}}$

What makes the estimation work is to show that the g_i functions are d-Ramanujan functions for all i less than √d-1/2.