Dtyjlui

While learning about the Zig Zag Theorem, I noticed that we are able to build an expander family using the $left(d^4, d, frac 14right)$ graph construction. I don't understand why this one actually exists.

My question stems from page 6 in http://www.math.mcgill.ca/goren/667.2010/Neil.pdf.

Thank you.

If we choose a random $d$-regular graph on $d^4$ vertices, then with positive probability its second eigenvalue is at most $frac d4$. This gives us the $(d^4, d, frac14)$-graph you want.

Actually, we expect the second eigenvalue to be $O(sqrt d)$, but it's harder to prove that.

We choose the random graph by taking the union of $d$ uniformly random matchings on $d^4$ vertices. This might sometimes be a multigraph, but we don't care; triple parallel edges are unlikely to occur, and we can fix all the double edges in a way that only improves expansion.

I'll assume that we can take $d$ sufficiently large for the approximations we want to hold; for small $d$, we have to do more messy calculations, and for very small $d$ we might have to manually look for the graph we want.

This is an application of the "trace method": we estimate the trace of the $k^{text{th}}$ power of the adjacency matrix of a random $d$-regular graph. This has a combinatorial interpretation: it counts closed walks of length $k$. It also gives the sum of the $k^{text{th}}$ powers of the eigenvalues. Here, we'll just take $k=10$.

We have three types of closed walks to care about:

1. Walks that follow a simple cycle of length $10$.


2. Walks that backtrack and don't include a cycle at all.


3. Walks that have a cycle at some point, but have fewer than $10$ distinct edges.

For the first kind: we have a bit under $(d^4)^{10}$ ways to choose which vertices the walk visits. Label the desired edges between them with which matching we want them to come from; this can be done in a bit fewer than $d^{10}$ ways that avoid the same label between multiple vertices. Then the probability that the edges we've asked for are present with probability a bit over $frac{1}{d^4}$ each, giving us $d^{40} cdot d^{10} cdot frac{1}{d^{40}} = d^{10}$ walks of this type in expectation, plus lower order terms.

The second kind of walk, we count deterministically in any $d$-regular graph. We have $d^4$ ways to choose the starting vertex, and since every edge is walked twice, we have at most $5$ edges to choose. Each new edge we choose can be chosen in fewer than $d$ ways, for $d^5$ choices. The number of shapes for this walk (e.g. walk 5 edges then walk back, or walk back and forth across an edge 5 times, etc.) is constant, so the contribution is $O(d^9)$.

The third kind of walk is counted similarly to the first, but more sloppily. Each of these has at most $9$ edges, and because they contain a cycle, they have at most as many vertices as edges. So for some $kle 9$, we choose the vertices in the walk (in about $d^{4k}$ ways), then label the edges with the matching they come from (in about $d^k$ ways), then find the probability that the resulting walk occurs in the graph (which is about $d^{-4k}$). The expected number of walks of this type is $O(d^k) = O(d^9)$ by multiplying these terms, and the number of different shapes is once again constant.

We conclude that the expected number of closed walks of length $10$ is $d^{10} + O(d^9)$. This means that there must exist a graph for which the number of closed walks of this length is at most this large.

We have $lambda_1^{10} + lambda_2^{10} + dots + lambda_{4d}^{10} le d^{10} + O(d^9)$ for this graph. We know $lambda_1 = d$ and the $lambda_3, dots, lambda_{4d}$ terms are nonnegative, so $lambda_2^{10} le O(d^9)$, or $|lambda_2| = O(d^{9/10})$. Take $d$ large enough, and $lambda_2 le frac d4$.