By Theorem 3.1 and Lemma 3.4 of Chapter 3,

Multiplying numerator and denominator by \(\mathrm{vol}\, \bar S\) and using \(1-(1-\lambda )^2=\lambda (2-\lambda )\) gives

Dividing numerator and denominator by \(\mathrm{vol}\, G\) and using \(\mathrm{vol}\, S=\mathrm{vol}\, G-\mathrm{vol}\, \bar S\), the denominator becomes \(1-\lambda (2-\lambda )\, \mathrm{vol}\, \bar S/\mathrm{vol}\, G\), which yields the first inequality. Since this denominator is at most \(1\), dropping it yields the second inequality \(\lambda (2-\lambda )\, \mathrm{vol}\, \bar S/\mathrm{vol}\, G\), as desired.

In the proof of Theorem 3.1 of Chapter 3, choose the polynomial \(p_t(\mathcal L)=I-\mathcal L\) and put \(Y=V(G)\setminus N(X)\). Then, with \(\psi _X,\psi _Y\) the characteristic functions,

the strict inequality holding because \(G\) is not complete. Hence \(\bar\lambda \sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, \bar X\, \mathrm{vol}\, Y\, \mathrm{vol}\, \bar Y} {\gt}\mathrm{vol}\, X\, \mathrm{vol}\, Y\), and squaring gives

Now take \(X=S\) and \(\bar Y=N(S)\), so \(\mathrm{vol}\, Y=\mathrm{vol}\, G-\mathrm{vol}\, N(S)\) and \(\mathrm{vol}\, \bar X=\mathrm{vol}\, G-\mathrm{vol}\, S\). Substituting,

and solving for \(\mathrm{vol}\, N(S)/\mathrm{vol}\, S\) gives \(\mathrm{vol}\, N(S)/\mathrm{vol}\, S{\gt}1/\bigl(\bar\lambda ^2+(1-\bar\lambda ^2)\, \mathrm{vol}\, S/\mathrm{vol}\, G\bigr)\), which equals the stated right-hand side since \(\mathrm{vol}\, S=\mathrm{vol}\, G-\mathrm{vol}\, \bar S\).

Let \(k\) be the common degree and let \(\psi _S\) be the characteristic function of \(S\). Since \(G\) is \(k\)-regular, the adjacency matrix \(A\) has eigenvalues \(k(1-\lambda _i)\) with orthonormal eigenfunctions \(\phi _i\), where \(\phi _0\) is constant. Write \(\psi _S=\sum _i a_i\phi _i\); then \(a_0^2=|S|^2/n\) and \(\sum _i a_i^2=|S|\). Because \((1-\lambda _0)^2=1\) and \((1-\lambda _i)^2\le \bar\lambda ^2\) for \(i\ge 1\) (with strict inequality somewhere as \(G\) is not complete),

On the other hand, counting common neighbors,

The summand is nonzero only for \(w\in N(S)\), so by the Cauchy–Schwarz inequality,

using \(\sum _{w}|N(w)\cap S|=\sum _{v\in S}|N(v)|=k|S|\). Combining with (6.1),

Let every vertex in \(X\) have degree \(k\); let \(\rho _i^2\) denote the eigenvalues of \(M^*M\) with largest \(\rho _0^2=k^2\) and second largest \(\rho ^2 k^2=\rho _1^2\). Writing the characteristic function \(\psi _S=\sum _i a_i(\cdot )\) in the eigenbasis of \(M^*M\), with \(a_0^2=|S|^2/n\) and \(\sum _i a_i^2=|S|\),

On the other hand,

by Cauchy–Schwarz. Combining with (6.3) yields \(|N(S)|\ge |S|/\bigl((1-\rho ^2)\, |S|/n+\rho ^2\bigr)\).

The argument is identical to that of Lemma 6.4 with the incidence matrix \(M\) replaced by the modified matrix \(\mathcal M\): the largest eigenvalue of \(\mathcal M^*\mathcal M\) is \(1\) with the degree-weighted constant vector as eigenfunction, and expanding \(\psi _S\) in the eigenbasis of \(\mathcal M^*\mathcal M\) together with the Cauchy–Schwarz estimate on \(\sum _{w\in Y}|N(w)\cap S|^2\) gives the stated bound.

Let \(\psi _1,\psi _2\) be as in Lemma 232. Let \(f:V\to \mathbb R\) satisfy \(\sum _{j,k}f(j,k)=0\), and define a measurable \(\phi :T\to \mathbb R\) by \(\phi (x,y)=f(j,k)\) whenever \(\tfrac jm\le x{\lt}\tfrac {j+1}m\) and \(\tfrac km\le y{\lt}\tfrac {k+1}m\). Then \(\int _T\phi =\tfrac 1{m^2}\sum _v f(v)=0\), and

Also \(\int _T\phi ^2=\tfrac 1{m^2}\sum _v f(v)^2\). Applying (6.4),

for every \(f\) with \(\sum f=0\). Since the left side is the Dirichlet sum of the \(12\)-regular graph \(M_n\), the Rayleigh quotient shows \(\lambda _1\ge \tfrac {2c}{12}=\tfrac {c}{6}=\tfrac {4-\sqrt{12}}{6}=\tfrac {2-\sqrt3}{3}\).

The number of walks of length \(k\) from \(v\) to \(u\) in \(M_n\) is exactly the \((u,v)\)-entry of \(A^k\), so the adjacency matrix of \(M_n^k\) is \(A^k\). If \(A\phi _i=\rho _i\phi _i\) then \(A^k\phi _i=\rho _i^k\phi _i\), giving the eigenvalues.

An input \(v\) must access \(6n\) of the middle vertices. After deleting the \(n\) possible blocked vertices in \(S\), the remaining set has at least \(5n\) inputs of \(M(n)\). For the Ramanujan graphs of degree \(k=6\) we have \(\lambda =1-\sqrt5/3\), so by Lemma 226 the neighborhood of a subset \(S\) of size \(5n\) has size at least

Since there are two copies of \(R(12n,5)\), there are at least \(\tfrac {27n}{2}\) neighbors of \(S\); among the \(\tfrac {27n}{2}\) outputs at least \(\tfrac {25n}{2}\) lie outside \(S\), which is more than half of the outputs of \(M(n)\). Hence \(M(n)\) is a major-access network, and the recursion for \(e(M(n))\) yields the stated bounds.

It suffices to show any input set \(X\) has at least \(|X|\) output neighbors; the case \(|X|=n/2\) is the hardest. If \(X\) contains at least \(\tfrac {n}{10}\) inputs among the first \(\tfrac n6\) (degree-\(5\)) inputs, we are done. Otherwise \(X\) contains at least \(\tfrac {2n}{5}\) inputs \(X'\) of the expander \(C\) (which has eigenvalue \(\lambda =1-\sqrt5/3\)), and the expansion bound gives

Hence \(X\) has at least \(|X|\) neighbors, so \(S(n)\) is a superconcentrator; the edge recursion gives the bound of at most \(76n\) edges. (Replacing \(S(\tfrac 56 n)\) by \(S((\tfrac 45+\epsilon )n)\) with \(\epsilon =.0288776\) reduces the count to \(69.8n\).)

Fix a vertex \(v\). Every other vertex lies within distance \(D\) of \(v\). There is \(1\) vertex at distance \(0\) (namely \(v\)), at most \(k\) vertices at distance \(1\), and, since each vertex at distance \(i\ge 1\) is adjacent to at most \(k-1\) vertices at distance \(i+1\) (one of its \(\le k\) neighbors lies closer to \(v\)), at most \(k(k-1)^{i-1}\) vertices at distance \(i\) for \(1\le i\le D\). Summing over \(i=0,\dots ,D\) gives at most \(M(k,D)\) vertices.

Fix a weight matrix \(W\) and let \(\lambda =\lambda _{max}(G_W)\). Let \(M_1\) have \((u,v)\)-entry \(\sqrt{w_u w_v}\); regarding \(T^{1/2}\mathbf1\) as a row vector, \(M_1=(T^{1/2}\mathbf1)(T^{1/2}\mathbf1)^*=T^{1/2}JT^{1/2}\), where \(w=\sum _v w_v\) and \(J\) is the all-ones matrix. Consider

Since \(M_1\) has rank one with eigenvector \(T^{1/2}\mathbf1\) and eigenvalue \(\| T^{1/2}\mathbf1\| ^2=\sum _v w_v=w\), and annihilates every eigenfunction of \(\mathcal L\) orthogonal to \(T^{1/2}\mathbf1\), the eigenfunctions of \(\mathcal L\) are eigenfunctions of \(M\): on \(T^{1/2}\mathbf1\) (an eigenfunction of \(\mathcal L\) for eigenvalue \(0\)), \(M\) acts as \(0-1+\tfrac {\lambda }{w}w=\lambda -1\); on any other eigenfunction \(\phi _i\) (with \(\mathcal L\phi _i=\lambda _i\phi _i\)), \(M\phi _i=(\lambda _i-1)\phi _i\). As \(\lambda =\lambda _{max}\ge \lambda _i\) for all \(i\), the maximum eigenvalue of \(M\) is \(\lambda -1\).

Let \(X\) be an independent set and \(M_X\) the principal submatrix of \(M\) on \(X\). On \(X\) there are no edges, so \(\mathcal L\) restricted to \(X\) is the identity; hence \(M_X=\tfrac {\lambda }{w}(M_1)_X=\tfrac {\lambda }{w}(T^{1/2}\mathbf1)_X (T^{1/2}\mathbf1)_X^*\), a rank-one matrix whose maximum eigenvalue is

Since the maximum eigenvalue of a principal submatrix of a symmetric matrix is at most that of the whole matrix (Rayleigh’s principle), \(\lambda -1\ge \tfrac {\lambda }{w}w(X)\). If \(\chi (G)=k\), partition \(V(G)\) into independent sets \(X_1,\dots ,X_k\); then \(\lambda -1\ge \tfrac {\lambda }{w}w(X_i)\) for each \(i\), and summing,

so \(\chi (G)=k\ge 1+\tfrac {1}{\lambda -1}\). Taking the maximum over all \(W\) gives \(\chi (G)\ge \sigma (G)\).

For any induced subgraph \(G'\) we have \(\chi (G)\ge \chi (G')\). Applying Theorem 255 to \(G'\) gives \(\chi (G')\ge 1+\max _W \tfrac {1}{\lambda _{max}(G’_W)-1}\); taking the maximum over all induced subgraphs \(G'\) yields the claim.

Specialize Corollary 256 to the unweighted case \(w_{uv}=1\) for \(u\sim v\), for which \(\lambda _{max}(G_W)=\lambda _{max}(G)\).

Let \(\omega (G)=k\); clearly \(k{\gt}1\). Let \(S=\{ v_1,\dots ,v_k\} \) be a maximum clique. Choose the weight matrix \(W\) with \(w_{uv}=w_{vu}=1\) for every edge \(\{ u,v\} \) inside \(S\) and \(0\) otherwise. Then \(\mathcal L_W\) restricted to \(S\) is the normalized Laplacian of the complete graph \(K_k\) (each \(v_j\) has weighted degree \(w_{v_j}=k-1\)), whose nonzero eigenvalues all equal \(\tfrac {k}{k-1}\). Let \(\theta =\exp (2\pi i/k)\ne 1\) be a \(k\)th root of unity and set \(f(v_j)=\theta ^j\). Then the (weighted) Rayleigh quotient equals

using \(\sum _j\theta ^{\pm j}=0\) and \(\sum _v w_v=k(k-1)\). Thus \(f\) is an eigenfunction realizing the value \(\tfrac {k}{k-1}\), which is the maximum eigenvalue of \(\mathcal L_W\); hence \(\lambda _{max}(G_W)=\tfrac {k}{k-1}\). Therefore

The left inequality is Theorem 258 and the right inequality is Theorem 255.

The inequality \(\omega (G)\le \sigma (G)\) is Theorem 258. The inequality \(\sigma (G)\le \vartheta (\bar G)\) follows from the reformulation Lemma 261 together with the eigenvalue formula for \(\vartheta \). The inequality \(\vartheta (\bar G)\le \chi (G)\) is Lovász’s classical bound.