4 A geometric view of expander graphs
Of all simple closed plane curves of a given length, which encloses the greatest area? (Answer: the circle.)
Symmetrizing a convex planar set about the \(x\)-axis (replacing each vertical slice \([y_1(x),y_2(x)]\) by the centred slice of equal length) preserves area and does not increase the perimeter.
\(\Phi _E(G,k)=\min _{|S|=k}|E(S,\overline S)|\).
\(\Phi _V(G,k)=\min _{|S|=k}|\Gamma (S)\setminus S|\).
\(Q_d\) is the graph on \(\{ 0,1\} ^d\) with edges between vectors of Hamming distance \(1\).
\(\Phi _E(Q_d,k)\ge k(d-\log _2k)\), with equality when \(k=2^\ell \) (a subcube).
If \(k=\sum _{i\le r}\binom di\) then \(\Phi _V(Q_d,k)=\binom d{r+1}\) (Hamming balls).
On \(I\times I\) (\(I=[0,1)\)), \(T(x,y)=(x+y,y)\) and \(S(x,y)=(x,x+y)\) (mod \(1\)); neighbours of \((x,y)\) are \(T^{\pm 1},S^{\pm 1}\) of it, a \(4\)-regular structure.
There is \(\epsilon {\gt}0\) such that every measurable \(A\) with \(\mu (A)\le \tfrac 12\) has \(\mu (\Gamma (A)\cup A)\ge (1+\epsilon )\mu (A)\).
Fix an orientation of \(E\). The \(V\times E\) matrix \(K\) has \(K_{u,e}=+1\) if \(e\) leaves \(u\), \(-1\) if \(e\) enters \(u\), else \(0\).
For \(f:V\to \mathbb {R}\), the gradient is \(fK\) (indexed by \(E\)), with \((fK)_e=f_u-f_v\) for \(e=(u,v)\). For \(g:E\to \mathbb {R}\), the divergence is \(Kg\).
\(L=L_G=KK^\top \), with \(L_{u,u}=\deg (u)\) and \(L_{u,v}=-1\) for \((u,v)\in E\).
\(fLf^\top =\| fK\| ^2=\sum _{(u,v)\in E}(f(u)-f(v))^2\).
\(fLf^\top =(fK)(fK)^\top =\| fK\| ^2\), and \((fK)_e=f(u)-f(v)\).
\(L_G\) is positive semidefinite; its smallest eigenvalue is \(0\) with constant eigenfunction.
For \(d\)-regular \(G\), \(L=dI-A\); \(\mathrm{spec}(L)\subseteq [0,2d]\), with smallest eigenvalue \(0\) and smallest positive eigenvalue \(d-\lambda _2\), the spectral gap.
\(\deg (u)=d\) gives \(L=dI-A\); eigenvalues of \(L\) are \(d-\mu \) for \(\mu \in \mathrm{spec}(A)\subseteq [-d,d]\), so the smallest is \(d-d=0\) and the smallest positive is \(d-\lambda _2\).
\(h(M)=\inf _A\mu _{n-1}(\partial A)/\min (\mu _n(A),\mu _n(M\setminus A))\).
The smallest positive Laplacian eigenvalue satisfies \(\lambda \ge h(M)^2/4\).
For \(B_f=\sum _{(x,y)\in E}|f_x^2-f_y^2|\) on a \(d\)-regular graph, \(B_f\le \sqrt{2d}\, \| fK\| \, \| f\| \).
By Cauchy–Schwarz, \(B_f=\sum _E|f_x+f_y|\, |f_x-f_y| \le \sqrt{\sum _E(f_x+f_y)^2}\sqrt{\sum _E(f_x-f_y)^2}\). The second factor is \(\| fK\| \); the first is \(\le \sqrt{2\sum _E(f_x^2+f_y^2)}=\sqrt{2d}\, \| f\| \) using \((a+b)^2\le 2(a^2+b^2)\) and \(d\)-regularity.
Order \(f_1\ge \dots \ge f_n\) with \(V^+=\mathrm{supp}(f)\), \(|V^+|\le n/2\). Then \(B_f\ge h(G)\, \| f\| ^2\).
Telescoping, \(B_f=\sum _{i}(f_i^2-f_{i+1}^2)|E([i],\overline{[i]})| \ge h\sum _{i\in V^+}(f_i^2-f_{i+1}^2)\, i=h\sum _{i\in V^+}f_i^2=h\| f\| ^2\), using \(|E([i],\overline{[i]})|\ge h\, i\) for \(i\le |V^+|\le n/2\).
For a \(d\)-regular graph, \(h(G)\ge \tfrac {d-\lambda _2}2\), equivalently \(\lambda _2\ge d-2h(G)\).
Let \(S\) attain \(h(G)\), \(|S|\le n/2\), and put \(f=|\overline S|\mathbf1_S-|S|\mathbf1_{\overline S}\perp \mathbf1\). Then \(\| f\| ^2=n|S||\overline S|\) and, using \(2|E(S)|=d|S|-|\partial S|\) and the analogue for \(\overline S\), \(\lambda _2\ge \frac{fAf^\top }{\| f\| ^2}=d-\frac{n|\partial S|}{|S||\overline S|} \ge d-2h(G)\), since \(|\overline S|\ge n/2\).
For a \(d\)-regular graph, \(h(G)\le \sqrt{2d(d-\lambda _2)}\).
Let \(g\) be a \(\lambda _2\)-eigenvector, \(f=g^+\) on \(V^+=\mathrm{supp}(g^+)\) with \(|V^+|\le n/2\). (i) \(fLf^\top \le (d-\lambda _2)\| f\| ^2\): for \(x\in V^+\), \((Lf)_x\le (Lg)_x=(d-\lambda _2)g_x\) since dropped terms have \(g_y\le 0\). (ii) Lemmas 90 and 89 give \(h\| f\| ^2\le B_f\le \sqrt{2d}\, \| fK\| \, \| f\| =\sqrt{2d\, fLf^\top }\, \| f\| \), so \(h^2/2d\le fLf^\top /\| f\| ^2\le d-\lambda _2\).
\(\Psi _E(G,k)=\min _{|S|\le k}\frac{|E(S,\overline S)|}{|S|}\), \(\Psi _V(G,k)=\min _{|S|\le k}\frac{|\Gamma (S)\setminus S|}{|S|}\), \(\Psi '_V(G,k)=\min _{|S|\le k}\frac{|\Gamma (S)|}{|S|}\).
For an \((n,d,\alpha )\)-graph and \(\rho {\gt}0\), \(\Psi '_V(G,\rho n)\ge \frac d2(1-\sqrt{1-4(d-1)/(d^2\alpha ^2)})(1-c\log d/\log (1/\rho ))\).
For an \((n,d,\alpha )\)-graph and \(\rho {\gt}0\), \(\Psi '_V(G,\rho n)\ge \frac1{\rho (1-\alpha ^2)+\alpha ^2}\).
For \(|S|=\rho n\), expand \(\mathbf1_S=\sum _ia_iv_i\). Then \(\| \hat A\mathbf1_S\| _2^2\le \tfrac {|S|^2}n+\alpha ^2(\| \mathbf1_S\| ^2-a_1^2) =\rho n(\rho +\alpha ^2(1-\rho ))\), while by Cauchy–Schwarz \(\| \hat A\mathbf1_S\| _2^2\ge |S|^2/|\Gamma (S)|\). Combining, \(|\Gamma (S)|/|S|\ge 1/(\rho (1-\alpha ^2)+\alpha ^2)\).
For fixed \(d\ge 3\) and every \(\delta {\gt}0\) there is \(\epsilon {\gt}0\) so that almost every \((n,d)\)-graph has \(\Psi _E(G,\epsilon n),\Psi _V(G,\epsilon n)\ge d-2-\delta \) and \(\Psi '_V(G,\epsilon n)\ge d-1-\delta \) (and \(\ge d-1-\delta \) in the bipartite case).
A hypergraph \(H=(V,E)\) has \(E\) a family of subsets of \(V\); it is \(r\)-uniform if every edge has size \(r\) (graphs are \(2\)-uniform).