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 subgraphMathworldPlanetmath induced by X is at most

12n(d|X|2+λ|X|(n-|X|))

where λ is the second largest eigenvalueMathworldPlanetmathPlanetmathPlanetmathPlanetmath of the adjacency matrixMathworldPlanetmath 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