# proof of Alon-Chung lemma

Let the vertices of $G$ be labeled by $\{1,2,\ldots,n\}$, and $\mathbf{x}$ be the column vector defined by

 $x_{i}=\begin{cases}1&\text{if vertex i is in X}\\ 0&\text{otherwise}\end{cases}$

for $i=1,2,\ldots,n$.

Let $\mathbf{A}$ denote the adjacency matrix of $G$. The number of edges in the subgraph induced by $X$ equals $\frac{1}{2}\mathbf{x}^{T}\mathbf{Ax}$, and we are going to show the following equivalent inequality,

 $\mathbf{x}^{T}\mathbf{Ax}\leq\frac{1}{n}\Big{(}d|X|^{2}+\lambda|X|(n-|X|)\Big{% )}.$

We label the eigenvalues of $\mathbf{A}$ in decreasing order as

 $\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}.$

The largest eigenvalue $\lambda_{1}$ is equal to the degree $d$, and we let $\mathbf{u}_{1}$ be the corresponding normalized eigenvector,

 $\mathbf{u}_{1}:=\frac{1}{\sqrt{n}}[1,1,\ldots,1]^{T}.$

As $\mathbf{A}$ is symmetric, there is a unitary matrix $\mathbf{U}$ that diagonalizes $\mathbf{A}$,

 $\mathbf{U}^{T}\mathbf{AU}=\begin{bmatrix}\lambda_{1}&&&\\ &\lambda_{2}&&\\ &&\ddots&\\ &&&\lambda_{n}\end{bmatrix}.$

The first column of $\mathbf{U}$ is the column vector $\mathbf{u}_{1}$. We obtain

 $\displaystyle\mathbf{x}^{T}\mathbf{Ax}$ $\displaystyle=$ $\displaystyle\sum_{k=1}^{n}\lambda_{k}(\mathbf{u}_{k}^{T}\mathbf{x})^{2}$ $\displaystyle\leq$ $\displaystyle d(\mathbf{u}_{1}^{T}\mathbf{x})^{2}+\lambda_{2}\sum_{k=2}^{n}(% \mathbf{u}_{k}^{T}\mathbf{x})^{2}.$

In the line above, the first term is

 $d(\mathbf{u}_{1}^{T}\mathbf{x})^{2}=\frac{d|X|^{2}}{n},$

while the summation is equal to

 $\sum_{k=2}^{n}(\mathbf{u}_{k}^{T}\mathbf{x})^{2}=\|\mathbf{x}\|^{2}-(\mathbf{u% }_{1}^{T}\mathbf{x})^{2}=|X|-\frac{|X|^{2}}{n}.$

Hence

 $\displaystyle\mathbf{x}^{T}\mathbf{Ax}$ $\displaystyle\leq$ $\displaystyle\frac{d|X|^{2}}{n}+\lambda_{2}\Big{(}|X|-\frac{|X|^{2}}{n}\Big{)}$ $\displaystyle=$ $\displaystyle\frac{1}{n}\Big{(}d|X|^{2}+\lambda_{2}|X|(n-|X|)\Big{)}.$
Title proof of Alon-Chung lemma ProofOfAlonChungLemma 2013-03-22 17:26:53 2013-03-22 17:26:53 kshum (5987) kshum (5987) 6 kshum (5987) Proof msc 05C50