proof of Alon-Chung lemma
Let the vertices of G be labeled by {1,2,…,n}, and 𝐱 be the column vector defined by
xi={1if vertex i is in X0otherwise |
for i=1,2,…,n.
Let 𝐀 denote the adjacency matrix of G. The number of edges in the subgraph
induced by X equals 12𝐱T𝐀𝐱, and we are going to show the following equivalent
inequality,
𝐱T𝐀𝐱≤1n(d|X|2+λ|X|(n-|X|)). |
We label the eigenvalues 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 eigenvector,
𝐮1:= |
As is symmetric, there is a unitary matrix
that diagonalizes ,
The first column of is the column vector . We obtain
In the line above, the first term is
while the summation is equal to
Hence
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 |