proof of Alon-Chung lemma

Let the vertices of G be labeled by {1,2,…,n}, and 𝐱 be the column vectorMathworldPlanetmath defined by

xi={1if vertex i is in X0otherwise

for i=1,2,…,n.

Let 𝐀 denote the adjacency matrixMathworldPlanetmath of G. The number of edges in the subgraphMathworldPlanetmath induced by X equals 12⁢𝐱T⁢𝐀𝐱, and we are going to show the following equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath inequality,


We label the eigenvaluesMathworldPlanetmathPlanetmathPlanetmathPlanetmath of 𝐀 in decreasing order as


The largest eigenvalue λ1 is equal to the degree d, and we let 𝐮1 be the corresponding normalized eigenvectorMathworldPlanetmathPlanetmathPlanetmath,


As 𝐀 is symmetricPlanetmathPlanetmathPlanetmathPlanetmath, there is a unitary matrixMathworldPlanetmath 𝐔 that diagonalizes 𝐀,


The first column of 𝐔 is the column vector 𝐮1. We obtain

𝐱T⁢𝐀𝐱 = ∑k=1nλk⁢(𝐮kT⁢𝐱)2
≤ d⁢(𝐮1T⁢𝐱)2+λ2⁢∑k=2n(𝐮kT⁢𝐱)2.

In the line above, the first term is


while the summation is equal to



𝐱T⁢𝐀𝐱 ≤ d⁢|X|2n+λ2⁢(|X|-|X|2n)
= 1n⁢(d⁢|X|2+λ2⁢|X|⁢(n-|X|)).
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