Expanders obtained from affine transformations

ABSTRACT

A bipartite graph Gn = (U, V, E) is said an (n, k, &dgr;) expander if |U| = |V| = n, |E| ≤ kn, and for any X ⫅ U, |&Ggr;Gn(X)| ≥ (1+&dgr;(1-|X|/n)) |X|, where &Ggr;Gn(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 &dgr; 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

• 1: N. Alon, "Eigenvalues and expanders" preprint.
• 2: N. Alon and V. D. Milman, "Eigenvalues, expanders and superconcentrators", Proc. 25th Ann. Symp. on Found. of Comput. Sci., (1984).
• 3: N. Alon, V. D, Milman and Z. Galil, "Better expanders and superconcentrators", in preparation.
• 4: F. R. K. Chung, "On concentrators, superconcentrators, and nonblocking networks", Bell system Tech. J., 58 (1979).
• 5: O. Gabber and Z. Galil, "Explicit constructions of linear-sized superconcentrators", J. Comput. System Sci., 22 (1981).
• 6: M. Klawe, "Nonexistence of one-dimensional expanding graphs", Proc. 22nd Ann. Symp. on Found. of Comput. Sci., (1981).
• 7: M. Klawe, "Limitations on explicit constructions of expanding graphs", SIAN J. Comput. 13 (1984).
• 8: G. A. Margulis, "Explicit construction of concentrators", Prob. Info. Trans., 9 (1975).
• 9: N. Pippenger, "Superconcentrator s", SIAM J. Comput. 6 (1977).

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

General Terms:
Algorithms, Theory, Verification