Eigenvalues and expansion of regular graphs

ABSTRACT

The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best-known explicit expanders. The spectral method yielded a lower bound of k/4 on the expansion of linear-sized subsets of k-regular Ramanujan graphs. We improve the lower bound on the expansion of Ramanujan graphs to approximately k/2. Moreover, we construct a family of k-regular graphs with asymptotically optimal second eigenvalue and linear expansion equal to k/2. This shows that k/2 is the best bound one can obtain using the second eigenvalue method. We also show an upper bound of roughly 1+k-1 on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound 2k-1 . As a byproduct, we obtain improved results on random walks on expanders and construct selection networks (respectively, extrovert graphs) of smaller size (respectively, degree) than was previously known.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 2: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 3: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 4: N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
• 5: N. Alon , Z. Galil , V. D. Milman, Better expanders and superconcentrators, Journal of Algorithms, v.8 n.5, p.337-347, Sept. 1987 [doi>10.1016/0196-6774(87)90014-9]
• 6: ~ALON, N., AND MILMAN, V.D. 1985. ,aq, isopcrimetric inequalities for graphs and superconcen- ~trators. J. Comb. Theory Ser. B 38, 73-88.
• 7: S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
• 8: ~BELLARE, M, GOLDREICH, O., AND GOLDWASSER, S. 1990. Randomness in interactive proofs. ~In Proceedings of the 31st Annual Symposium on Fozmdatiolls of Computer Science. IEEE, New ~York, pp. 563-572.
• 9: ~BIEN, F. 1989. Constructions of telephone networks by group representations. Notices Amer. ~Muth Soc. 36, 1, 5-22.
• 10: ~BOLLOBAS, B. 1990. Graph Theory. Springer-Verlag, New York.
• 11: Andrei Z. Broder , Alan M. Frieze , Eli Shamir , Eli Upfal, Near-perfect Token Distribution, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.308-317, July 13-17, 1992
• 12: Marshall W Buck, Expanders and diffusers, SIAM Journal on Algebraic and Discrete Methods, v.7 n.2, p.282-304, April 1986 [doi>10.1137/0607032]
• 13: ~FRIEDMAN, J. 1991. On the second eigenvalue and random walks in random regular graphs. ~Combmatotica 11, 4, 331-362.
• 14: FRIEDMAN, J. 1991. Some geometric aspects of graphs and their elgenfunctions. Tech. Rep. ~Dept. Computer Science, Princeton Univ., Princeton, N.J.
• 15: GABBER, O., AND GALIL, Z. 1981. Explicit constructions of linear sized superconcentrators. J. ~Comput. System Sct. 22, 3, 407-420.
• 16: ~GOLDRE1CH, O, IMPAGLIAZZO, R., LEVIN, L., VENKATESAN, R., AND ZUCKERMAN, D. 1990. ~Security preserving amplification of hardness. In Proceedings of the 31st Annual Symposium on ~Fozmdatwns of Computer Sctence. IEEE Computer Society Press, New York, pp. 318-326.
• 17: Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
• 18: Nabil Kahale, Better expansion for Ramanujan graphs, Proceedings of the 32nd annual symposium on Foundations of computer science, p.398-404, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185397]
• 19: ~KAHALE, N. 1993a. On the second eJgenvalue and linear expansion of regular graphs. In ~DIMACS Serws in Discrete Mathematzcs and Theoretical Compz~ter Science 10, 49-62.
• 20: Nabil Kahale, Expander graphs, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 21: ~LEIGHTON, T., AND MAGGS, B. 1989. Fast algorithms for routing around faults on multibutter- ~flies. In Proceedings of the 30th Annual Symposium on Foztndatzolzs of Computer Science. IEEE, ~New York.
• 22: LUBOTZKY, A. D~screte groups, expandmgs graphs and mvanant measures. To appear.
• 23: LUBOTZK'~, A., PHILLIPS, R., AND SARNAK, P. 1988. Ramanujan graphs. Combinatorica 8, 3, ~261-277.
• 24: ~MARGULIS, G.A. 1973. Explicit construcnons of concentrators. Prob. Pereda~il~zf. 9, 4, 71-80.
• 25: ~MARGULIS, G.A. 1988. Explicit group-theoretical constructions of combinatorial schemes and ~their applications to the design of expanders and concentrators. Prob. PeredaEi Inf. 24, 1, ~51 - 60.
• 26: A. Nilli, On the second eigenvalue of a graph, Discrete Mathematics, v.91 n.2, p.207-210, Aug. 28, 1991 [doi>10.1016/0012-365X(91)90112-F]
• 27: Nicholas Pippenger, Selection networks, SIAM Journal on Computing, v.20 n.5, p.878-887, Oct. 1991 [doi>10.1137/0220054]
• 28: Nicholas Pippenger, Self-routing superconcentrators, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.355-361, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167195]
• 29: ~sARNAK, P. 1990. Some applications of modular forms. Cambridge University Press. Cambridge, ~Mass.
• 30: ~SENETA, E. 1981. Non-lzegatfi'e matrtces and Markot' chains. Springer-Verlag, New York.
• 31: ~STRANG, G. 1988. LmearAlbegra and it6 Apphcatlons. Harcourt Brace Jovanovich, San Dingo.
• 32: ~TANNER, R.M. 1984. Explicit construction of concentrators from generahzed n-gons. SIAM 1. ~Algebratc Dtsc. Meth. 5, 3, 287-294.
• 33: E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
• 34: ~VALIANT, L. 1976. Graph theoretic properties in computational complexity. J. Compat Syst. ~Sci. 13, 278-285.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  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

Keywords:
Ramanujan graphs, eigenvalues, expander graphs, induced subgraphs, load balancing, random walks, selection networks