AbstractThe 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 + \sqrt{k-1} on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound 2\sqrt{k-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. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in:
- Nabil Kahale. Better expansion for Ramanujan graphs. In 32nd Annual Symposium on Foundations of Computer Science, pages 398-404, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Nabil Kahale. On the second eigenvalue and linear expansion of regular graphs. In 33rd Annual Symposium on Foundations of Computer Science, pages 296-303, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Eigenvalues, expander graphs, induced subgraphs, load balancing, Ramanujan graphs, random walks, selection networks
Selected papers that cite this one
- Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability -- towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998.
- Miltos D. Grammatikakis, D. Frank Hsu, and Jop F. Sibeyn. Packet routing in fixed-connection networks: A survey. Journal of Parallel and Distributed Computing, 54(2):77-132, 1 November 1998.
- Bruce M. Maggs and Berthold Vöcking. Improved routing and sorting on multibutterflies. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 517-530, El Paso, Texas, 4-6 May 1997.
Selected references
- Miklós Ajtai, János Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 132-140, New York City, 25-27 May 1987.
- Sanjeev Arora, Tom Leighton, and Bruce Maggs. On-line algorithms for path selection in a nonblocking network (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 149-158, Baltimore, Maryland, 14-16 May 1990.
- Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Randomness in interactive proofs. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 563-572, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman. Security preserving amplification of hardness. In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 318-326, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Nabil Kahale. Better expansion for Ramanujan graphs. In 32nd Annual Symposium on Foundations of Computer Science, pages 398-404, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Nabil Kahale. On the second eigenvalue and linear expansion of regular graphs. In 33rd Annual Symposium on Foundations of Computer Science, pages 296-303, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Tom Leighton and Bruce Maggs. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. In 30th Annual Symposium on Foundations of Computer Science, pages 384-389, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Nicholas Pippenger. Self-routing superconcentrators. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 355-361, San Diego, California, 16-18 May 1993.
- Eli Upfal. An O(log N) deterministic packet routing scheme (preliminary version). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 241-250, Seattle, Washington, 15-17 May 1989.