Expanders obtained from affine transformations

Shuji Jimbo, Akira Maruoka

1985 · 27 citations · 6 references

Concepts

Abstract

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.

References

6