1985 · 27 citations · 6 references
Natural SciencesMathematicsAlgebraAffine GeometryGeometric TransformationsHomogeneous Transformation MatricesLie AlgebrasAffine TransformationsExpansionTransformations
A bipartite graph Gn = (U, V, E) is said an (n, k, d) expander if |U| = |V| = n, |E| ≤ kn, and for any X s U, |GGn(X)| ≥ (1+d(1-|X|/n)) |X|, where GGn(X) is the set of nodes in V connected to nodes in X with edges in E. In this paper we show that the problem of estimating the coefficient d of a bipartite graph is reduced to that of estimating the eigenvalue of a matrix related to the graph. As a result we give an explicit construction of (n, 5, 1 - 5/8 √2) expanders. By applying Gabber and Galil's construction to these expanders we obtain n-superconcentrators with 248n edges.
6
COMBINATORICA · 1986 · 1.2K citations
Eigenvalues, Expanders And Superconcentrators
Noga Alon, Vitali Milman · 2005 · 69 citations