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,

𝐱T⁢𝐀𝐱≤1n⁢(d⁢|X|2+λ⁢|X|⁢(n-|X|)).

We label the eigenvaluesMathworldPlanetmathPlanetmathPlanetmathPlanetmath of 𝐀 in decreasing order as

λ1≥λ2≥…≥λn.

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

𝐮1:=1n⁢[1,1,…,1]T.

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

𝐔T⁢𝐀𝐔=[λ1λ2⋱λn].

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

d⁢(𝐮1T⁢𝐱)2=d⁢|X|2n,

while the summation is equal to

∑k=2n(𝐮kT⁢𝐱)2=∥𝐱∥2-(𝐮1T⁢𝐱)2=|X|-|X|2n.

Hence

𝐱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