5 Extremal problems on spectrum and expansion
\(C_k=\binom {2k}k/(k+1)\), counting balanced bracket sequences; \(C_k=\Theta (4^k k^{-3/2})\).
\(\mathbf{T}_d\) is the unique infinite connected acyclic graph with every vertex of degree \(d\) (the universal cover of every \(d\)-regular graph).
\(\Phi _E(\mathbf{T}_d,k)=k(d-2)+2\) and \(h(\mathbf{T}_d)=d-2\); hence every \((n,d)\)-graph has \(\Phi _E(G,k)\le k(d-2)+2\).
A minimizing set is a subtree, with \(|E(S)|=|S|-1\); counting directed edges, \(\Phi _E(\mathbf{T}_d,k)=kd-2(k-1)=k(d-2)+2\), and dividing by \(k\) gives \(h(\mathbf{T}_d)=d-2\).
\(A_T\) acts on \(\ell _2(V(\mathbf{T}_d))\); \(\lambda \in \mathrm{spec}(A_T)\) iff \(A_T-\lambda I\) is not invertible.
\(\mathrm{spec}(A_T)=[-2\sqrt{d-1},\, 2\sqrt{d-1}]\).
\(\lambda \in \mathrm{spec}(A_T)\) iff \(\delta _v\notin \mathrm{Range}(\lambda I-A_T)\). Seeking a spherical solution \(f\) of \(\delta _v=(\lambda I-A)f\) gives the recurrence \(\lambda x_i=x_{i-1}+(d-1)x_{i+1}\) with characteristic roots \(\rho _{1,2}=\frac{\lambda \pm \sqrt{\lambda ^2-4(d-1)}}{2(d-1)}\). For \(|\lambda |{\lt}2\sqrt{d-1}\) the roots have modulus \((d-1)^{-1/2}\) and \(f\notin \ell _2\) (as \((d-1)^i\) vertices at level \(i\)), so \(\lambda \) is in the spectrum; for \(|\lambda |{\gt}2\sqrt{d-1}\) an \(\ell _2\) solution exists, so \(\lambda \) is not.
\(\rho (\mathbf{T}_d)=2\sqrt{d-1}\).
\(t_{2k}\) is the number of closed walks of length \(2k\) from a fixed vertex of \(\mathbf{T}_d\) (the analogous count in any \(d\)-regular graph is \(\ge t_{2k}\)).
\(t_{2k}\ge C_k(d-1)^k=\Theta ((2\sqrt{d-1})^{2k}k^{-3/2})\).
Each closed walk has a sign pattern (away/toward \(v\)) that is a balanced bracket sequence, \(C_k\) of them; each admits \(\ge (d-1)^k\) walks (at least \(d-1\) choices per away-step). Catalan asymptotics give the estimate.
The largest eigenvalue \(\mu \) of the height-\(k\) tree \(\mathbf{T}_d^{(k)}\) has a unique, nonnegative, spherically symmetric eigenfunction \(g\), with \(g_i\) on level \(i\) satisfying \(\mu g_0=dg_1\), \(\mu g_i=g_{i-1}+(d-1)g_{i+1}\), \(g_{k+1}=0\).
Perron–Frobenius gives uniqueness and nonnegativity; spherical symmetry follows as in Theorem 102.
For \(f\) built from a nonincreasing \(g\) supported on the two distance-balls around far vertices \(s,t\): \((Af)_v\ge \mu f_v\) on the \(s\)-side and \((Af)_v\le \mu f_v\) on the \(t\)-side.
For \(v\) at level \(i\) with \(p\) neighbours below, \(q\) at level, \(d-p-q\) above, \((Af)_v=c_1(pg_{i-1}+qg_i+(d-p-q)g_{i+1})\ge c_1(g_{i-1}+(d-1)g_{i+1})=\mu f_v\), using monotonicity of \(g\) and the recurrence.
\(\lambda _2(G)\ge \mu \), the top eigenvalue of \(\mathbf{T}_d^{(k)}\).
With the \(\pm \) choice of constants making \(f\perp \mathbf1\), the contributions of both sides give \(fAf^\top \ge \mu \| f\| ^2\), so by the variational principle \(\lambda _2\ge \mu \).
There is \(c\) such that every \((n,d)\)-graph of diameter \(\Delta \) has \(\lambda _2\ge 2\sqrt{d-1}(1-c/\Delta ^2)\).
By Corollary 108, \(\lambda _2\ge \mu \). The explicit solution \(h_i=(d-1)^{-i/2}\sin ((k+1-i)\theta _0)\) of the recurrence in Claim 106 (with \(\theta _0\) the smallest root of the boundary condition, \(0{\lt}\theta _0{\lt}\pi /(k+1)\)) gives \(\mu =2\sqrt{d-1}\cos \theta _0\). With \(k=\lfloor \Delta /2\rfloor -1\), \(\cos \theta _0{\gt}1-c/\Delta ^2\).
Every \((n,d)\)-graph has \(\lambda _2\ge 2\sqrt{d-1}(1-O(1/\log ^2n))\).
An \((n,d)\)-graph has diameter \(\Delta =\Omega (\log _{d-1}n)\); substitute into Theorem 109.
For every \(d,\epsilon \) there is \(c(\epsilon ,d){\gt}0\) so that every \((n,d)\)-graph has \(\ge cn\) eigenvalues \({\gt}2\sqrt{d-1}-\epsilon \).
With \(n_\epsilon \) the number of large eigenvalues, \(\operatorname {tr}(A+dI)^k\le (2d)^kn_\epsilon +(d+2\sqrt{d-1}-\epsilon )^kn\); on the other hand \(\operatorname {tr}(A+dI)^k\ge \tfrac {c’}{k^{3/2}}n(d+2\sqrt{d-1})^k\) using \(\operatorname {tr}(A^{2l})\ge n\, t_{2l}\) and Lemma 105. Comparing and choosing \(k=\Omega (\tfrac d\epsilon \log \tfrac d\epsilon )\) gives \(n_\epsilon /n\ge c\).
\(L_n\) is a \(K_n\) glued to a path \(P_{n+1}\) at a vertex; it has average degree \(\Theta (n)\) but \(\lambda (L_n)\le 2\) (showing Alon–Boppana fails for irregular graphs).
\(\lambda _1\ge d\), where \(d=2|E|/n\) is the average degree.
The Rayleigh quotient of \(\mathbf1\) is \(\mathbf1A\mathbf1^\top /n=2|E|/n=d\), and \(\lambda _1\) is the maximum.
If the average degree is \(\ge d\) after deleting any radius-\(r\) ball, then \(\lambda (G)\ge 2\sqrt{d-1}(1-c\log r/r)\).
A \(d\)-regular \(G\) is Ramanujan if \(\lambda (G)\le 2\sqrt{d-1}\).
For every prime power \(q=p^k\) there are infinitely many \((q+1)\)-regular Ramanujan graphs.
For distinct primes \(p,q\equiv 1\ (4)\), \(X^{p,q}\) is a \((p+1)\)-regular Cayley graph of \(\mathrm{PGL}(2,q)\) with generators the \(p+1\) Jacobi solutions of \(a_0^2+a_1^2+a_2^2+a_3^2=p\).
For every \(d\ge 3\) there are arbitrarily large \(d\)-regular Ramanujan graphs.