Alon-Chung lemma

Let $G=(V,E)$ be a undirected graph of $n$ vertices such that the degree of each vertex is equal to $d$. Let $X$ be a subset of $V$. Then the number of edges in the subgraph induced by $X$ is at most

 $\frac{1}{2n}\Big{(}d|X|^{2}+\lambda|X|(n-|X|)\Big{)}$

where $\lambda$ is the second largest eigenvalue of the adjacency matrix of $G$.

Reference: N. Alon and F. R. K. Chung, “Explicit construction of linear sized tolerant networks,” Discrete Math., vol. 72, pp. 15-19, 1988.

Title Alon-Chung lemma AlonChungLemma 2013-03-22 17:26:47 2013-03-22 17:26:47 kshum (5987) kshum (5987) 6 kshum (5987) Theorem msc 05C50