请输入您要查询的字词:

 

单词 ProofOfAlonChungLemma
释义

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+λ2k=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|)).
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 23:36:59