7 The spectrum of random graphs
\(G(n,p)\) is the Erdős–Rényi model (each edge independently with probability \(p\)). The random \((n,d)\)-graph model samples \(d\)-regular graphs (via the configuration/permutation model).
Estimate \(\operatorname {tr}(A^{2k})=\sum _i\lambda _i^{2k}\), the number of closed length-\(2k\) walks; subtracting \(\lambda _1^{2k}\) and taking \(2k\)-th roots bounds the second eigenvalue.
For a random symmetric \(A_n\) with i.i.d. entries (variance \(\sigma ^2\), finite moments), the empirical eigenvalue distribution of \(A_n/(2\sigma \sqrt n)\) converges to the semicircle \(\frac2\pi \int _{-1}^x\sqrt{1-z^2}\, dz\).
\(t_{2s+1}=0\) and \(t_{2s}=\sum _{j=1}^s\binom {2s-j}s\frac j{2s-j}d^j(d-1)^{s-j}\).
Trees are bipartite, so \(t_{2s+1}=0\). A closed walk gives a nonnegative lattice path \(\delta _0=0,\dots ,\delta _{2s}=0\) with \(\pm 1\) steps; among such paths exactly \(j\) visits to level \(0\) number \(\binom {2s-j}s\frac j{2s-j}\), and each path admits \(d^j(d-1)^{s-j}\) walks (factor \(d\) at the root, \(d-1\) elsewhere on away-steps; toward-steps are forced).
If \(d\)-regular \(G_n\) have \(o(|V|)\) cycles of each fixed length, their empirical eigenvalue distribution converges to the Kesten–McKay law supported on \([-2\sqrt{d-1},2\sqrt{d-1}]\).
For a random symmetric \(A\) with independent bounded mean-zero entries (variance \(\sigma ^2\)), w.h.p. all eigenvalues satisfy \(|\lambda _i|{\lt}2\sigma \sqrt n+O(n^{1/3}\log n)\).
Choose \(d\) independent uniform permutations \(\pi _1,\dots ,\pi _d\in S_n\) and add edges \((v,\pi _i(v))\); this is contiguous with the uniform \((n,2d)\)-model.
For the walk transition matrix \(P\) with \(\rho =\max (|\mu _2|,|\mu _n|)\), \(\mathbb {E}[\rho ]\le (\mathbb {E}[\operatorname {tr}(P^{2k})]-1)^{1/2k}\) and \(\mathbb {E}[\operatorname {tr}(P^{2k})]=n\Pr [\omega (1)=1]\), where \(\omega \) is a uniform word of length \(2k\) over \(\{ \pi _i^{\pm 1}\} \).
\(\rho ^{2k}\le \operatorname {tr}(P^{2k})-1\) by isolating \(\mu _1^{2k}=1\); Jensen gives \(\mathbb {E}[\rho ]\le (\mathbb {E}\rho ^{2k})^{1/2k}\). Closed walks correspond to words \(\omega \) with \(\omega (i)=i\), so \(\operatorname {tr}(P^{2k})\) counts fixed points of \(\omega \) and, by symmetry, \(\mathbb {E}[\operatorname {tr}(P^{2k})]=n\Pr [\omega (1)=1]\).
A word reduces by deleting adjacent \(\pi _j\pi _j^{-1}\) pairs. A reduced word is bad if it has the form \(\omega _a\omega _b^j\omega _a^{-1}\) (\(j\ge 2\), or empty), else good.
A uniform length-\(2k\) word reduces to a bad word with probability \(O(k^2(2/d)^k)\).
Bracket–star sequences encoding length-\(2k\) words reducing to length \(2l\) number \(\le \binom {2k}{k-l}\); matching a fixed sequence costs \((2d)^{-(k-l)}\), and badness of the reduced word costs a further \((2d)^{-l}\) (first half determines the second), after choosing \(|\omega _a|,|\omega _b|\) (\(k^2\) ways). Summing gives \(\le k^2(2/d)^k\).
Exposing a good word’s walk step by step, a step is free if the image was undetermined; a coincidence is a free step landing on a previously visited vertex. Each \(\Pr [C_i\mid \text{history}]\le 2k/(n-2k)\).
The probability of \(\ge 2\) coincidences is \(O(k^4/n^2)\).
Over \(\le (2k)^2\) position pairs, each pair of coincidences has probability \(\le (2k/(n-2k))^2\).
For a good word of length \(s\le 2k\), the probability of exactly one coincidence and ending at vertex \(1\) is \(\le 1/(n-2k)\).
After one coincidence the walk forms a cycle with a tail; goodness forbids looping, forcing \(\omega =\omega _a\omega _b\omega _a^{-1}\). The event is contained in one free step hitting a specific vertex, of probability \(\le 1/(n-2k)\).
Almost every \(2d\)-regular graph has \(\lambda (G)=O(d^{3/4})\).
For almost all high lifts of any \(G\), all new eigenvalues are bounded by \(\rho (\hat G)+o(1)\).
For almost all high lifts of \(G\) (top eigenvalue \(\lambda _1\), universal cover spectral radius \(\rho \)), all new eigenvalues are \(\le \sqrt{\lambda _1\rho }+o(1)\).
Theorem 148 with \(\lambda _1=2d\), \(\rho =2\sqrt{d-1}\) recovers \(O(d^{3/4})\).
Substitute: \(\sqrt{2d\cdot 2\sqrt{d-1}}=O(d^{3/4})\).
For every \(\epsilon {\gt}0\), a random \((n,d)\)-graph has \(\Pr [\lambda (G)\le 2\sqrt{d-1}+\epsilon ]=1-o_n(1)\).