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 14\right)$ 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:
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 $k\le 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$.