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}\left(d{|X|}^2+\lambda |X|(n-|X|)\right)$$

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
Canonical name	AlonChungLemma
Date of creation	2013-03-22 17:26:47
Last modified on	2013-03-22 17:26:47
Owner	kshum (5987)
Last modified by	kshum (5987)
Numerical id	6
Author	kshum (5987)
Entry type	Theorem
Classification	msc 05C50