proof of Alon-Chung lemma

Let the vertices of $G$ be labeled by $\{1,2,\mathrm{\dots },n\}$, and $𝐱$ be the column vector defined by

for $i=1,2,\mathrm{\dots },n$.

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

$${𝐱}^T\mathrm{𝐀𝐱}\le \frac{1}{n}\left(d{|X|}^2+\lambda |X|(n-|X|)\right).$$

We label the eigenvalues of $𝐀$ in decreasing order as

$${\lambda }_1\ge {\lambda }_2\ge \mathrm{\dots }\ge {\lambda }_n.$$

The largest eigenvalue ${\lambda }_1$ is equal to the degree $d$, and we let ${𝐮}_1$ be the corresponding normalized eigenvector,

$${𝐮}_1:=\frac{1}{\sqrt{n}}{[1,1,\mathrm{\dots },1]}^T.$$

As $𝐀$ is symmetric, there is a unitary matrix $𝐔$ that diagonalizes $𝐀$,

The first column of $𝐔$ is the column vector ${𝐮}_1$. We obtain

${𝐱}^T\mathrm{𝐀𝐱}$ $=$ ${\displaystyle \sum _{k=1}^n}{\lambda }_k{({𝐮}_k^T𝐱)}^2$

$\le$ $d{({𝐮}_1^T𝐱)}^2+{\lambda }_2{\displaystyle \sum _{k=2}^n}{({𝐮}_k^T𝐱)}^2.$

In the line above, the first term is

$$d{({𝐮}_1^T𝐱)}^2=\frac{d{|X|}^2}{n},$$

while the summation is equal to

$$\sum _{k=2}^n{({𝐮}_k^T𝐱)}^2={\parallel 𝐱\parallel }^2-{({𝐮}_1^T𝐱)}^2=|X|-\frac{{|X|}^2}{n}.$$

Hence

${𝐱}^T\mathrm{𝐀𝐱}$ $\le$ ${\displaystyle \frac{d{|X|}^2}{n}}+{\lambda }_2\left(|X|-{\displaystyle \frac{{|X|}^2}{n}}\right)$

$=$ ${\displaystyle \frac{1}{n}}\left(d{|X|}^2+{\lambda }_2|X|(n-|X|)\right).$

Title	proof of Alon-Chung lemma
Canonical name	ProofOfAlonChungLemma
Date of creation	2013-03-22 17:26:53
Last modified on	2013-03-22 17:26:53
Owner	kshum (5987)
Last modified by	kshum (5987)
Numerical id	6
Author	kshum (5987)
Entry type	Proof
Classification	msc 05C50