2 Graph expansion and eigenvalues
Unless stated otherwise \(G=(V,E)\) is undirected, \(d\)-regular, with \(n=|V|\) (self-loops/multi-edges allowed). For \(S,T\subseteq V\), \(E(S,T)=\{ (u,v):u\in S,v\in T,(u,v)\in E\} \) is a set of directed edges; \(\Gamma (S)\) is the neighbourhood of \(S\).
The edge boundary is \(\partial S=E(S,\overline S)\); the expansion ratio is \(h(G)=\min _{|S|\le n/2}\frac{|\partial S|}{|S|}\).
A sequence \(\{ G_i\} \) of \(d\)-regular graphs of increasing size is a family of expanders if \(h(G_i)\ge \epsilon \) for some \(\epsilon {\gt}0\), all \(i\).
\(\{ G_i\} \) (on \(n_i\) vertices, \(n_{i+1}\le n_i^2\)) is mildly explicit if \(G_j\) is computable in time \(\mathrm{poly}(j)\), and very explicit if the \(k\)-th neighbour of \(v\) in \(G_i\) is computable in time \(\mathrm{poly}(|(i,v,k)|)\).
\(G_m\) has vertices \(\mathbb {Z}_m\times \mathbb {Z}_m\); \((x,y)\) joins \((x\pm y,y)\), \((x\pm (y+1),y)\), \((x,y\pm x)\), \((x,y\pm (x+1))\) (mod \(m\)); \(8\)-regular and very explicit.
For prime \(p\), \(V_p=\mathbb {Z}_p\), \(x\) joins \(x\pm 1\) and \(x^{-1}\) (\(0^{-1}:=0\)); \(3\)-regular, expansion by Selberg’s \(3/16\) theorem, mildly explicit.
The adjacency matrix \(A=A(G)\) has \((u,v)\) entry the number of edges between \(u,v\). It is real symmetric with eigenvalues \(\lambda _1\ge \dots \ge \lambda _n\) (the spectrum) and orthonormal eigenbasis \(v_1,\dots ,v_n\).
A real symmetric matrix has real eigenvalues and an orthonormal eigenbasis.
For real vectors, \(|\langle x,y\rangle |\le \| x\| _2\, \| y\| _2\).
An irreducible nonnegative matrix has a positive real eigenvalue equal to its spectral radius, with a positive eigenvector of multiplicity one.
For a symmetric \(A\) with eigenvalues \(\lambda _1\ge \dots \ge \lambda _n\) and top eigenvector \(v_1\), \(\lambda _1=\max _x\frac{x^\top Ax}{\| x\| ^2}\) and \(\lambda _2=\max _{x\perp v_1}\frac{x^\top Ax}{\| x\| ^2}\).
For \(d\)-regular \(G\): (i) \(\lambda _1=d\) with eigenvector \(\mathbf1/\sqrt n\); (ii) \(G\) is connected iff \(\lambda _1{\gt}\lambda _2\); (iii) \(G\) is bipartite iff \(\lambda _1=-\lambda _n\).
(i) \(A\mathbf1=d\mathbf1\) and Perron–Frobenius makes \(d\) the top eigenvalue. (ii) The multiplicity of \(d\) is the number of components. (iii) For connected \(G\), \(-d\) is an eigenvalue iff \(G\) is bipartite (a \(\pm 1\) eigenvector splits \(V\)).
Set \(\lambda (G)=\max (|\lambda _2|,|\lambda _n|)\). An \(n\)-vertex \(d\)-regular graph is an \((n,d)\)-graph; it is an \((n,d,\alpha )\)-graph if \(\lambda (G)\le \alpha d\). The spectral gap is \(d-\lambda _2\).
For a \(d\)-regular graph, \(\frac{d-\lambda _2}2\le h(G)\le \sqrt{2d(d-\lambda _2)}\).
For a \(d\)-regular graph on \(n\) vertices with \(\lambda =\lambda (G)\) and all \(S,T\subseteq V\), \(\bigl|\, |E(S,T)|-\frac{d|S||T|}n\bigr|\le \lambda \sqrt{|S||T|}\).
Expand \(\mathbf1_S=\sum _i\alpha _iv_i\), \(\mathbf1_T=\sum _j\beta _jv_j\) in the eigenbasis (\(v_1=\mathbf1/\sqrt n\)). Then \(|E(S,T)|=\mathbf1_S^\top A\mathbf1_T=\sum _i\lambda _i\alpha _i\beta _i =d\tfrac {|S||T|}n+\sum _{i\ge 2}\lambda _i\alpha _i\beta _i\), since \(\alpha _1=|S|/\sqrt n\), \(\beta _1=|T|/\sqrt n\). Hence by the definition of \(\lambda \) and Cauchy–Schwarz the deviation is \(\le \lambda \sum _{i\ge 2}|\alpha _i\beta _i|\le \lambda \| \alpha \| _2\| \beta \| _2 =\lambda \sqrt{|S||T|}\).
If \(\bigl|\, |E(S,T)|-\tfrac {d|S||T|}n\bigr|\le \rho \sqrt{|S||T|}\) for all disjoint \(S,T\), then \(\lambda \le O(\rho (1+\log (d/\rho )))\), and this is tight.
An independent set in an \((n,d,\alpha )\)-graph has \(\le \alpha n\) vertices.
With \(T=S\) and \(|E(S,S)|=0\), the mixing lemma gives \(\tfrac {d|S|^2}n\le \lambda |S|\le \alpha d|S|\).
An \((n,d,\alpha )\)-graph has \(\chi (G)\ge 1/\alpha \).
Each colour class is independent of size \(\le \alpha n\), so \(\ge 1/\alpha \) classes are needed.
An \((n,d,\alpha )\)-graph has diameter \(O(\log n)\).
For \(S=B(x,r)\) with \(|S|\le n/2\), the mixing lemma gives \(|E(S,\overline S)|/|S|\ge d((1-\alpha )-|S|/n)\), so \(|B(x,r+1)|\ge (1+\epsilon )|B(x,r)|\) with \(\epsilon =\tfrac 12-\alpha \). Geometric growth reaches \(n/2\) within \(O(\log n)\) steps; applying this from any vertex bounds the diameter.
Every \((n,d)\)-graph has \(\lambda \ge 2\sqrt{d-1}-o_n(1)\).
Proved in the extremal chapter (Theorem 109) via closed walks in the \(d\)-regular tree.
Every \((n,d)\)-graph has \(\lambda \ge \sqrt d\, (1-o_n(1))\).
\(\operatorname {tr}(A^2)\) counts closed walks of length \(2\), so \(\operatorname {tr}(A^2)\ge nd\). Also \(\operatorname {tr}(A^2)=\sum _i\lambda _i^2\le d^2+(n-1)\lambda ^2\). Hence \(\lambda ^2\ge d\tfrac {n-d}{n-1}\).