Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Reingold, Vadhan and Wigderson [21] introduced the graph zig-zag product. This product combines a large graph and a small graph into one graph, such that the resulting graph inherits its size from the large graph, its degree from the small graph and its spectral gap from both. Using this product they gave the first

fully-explicit combinatorial construction of expander graphs. They showed how to construct D-regular graphs having spectral gap 1-O(D^-1/3). In the same paper, they posed the open problem of whether a similar graph product could be used to achieve the almost-optimal spectral gap 1-O(D^-1/2).

In this paper we propose a generalization of the zig-zag product that combines a large graph and several small graphs. The new product gives a better relation between the degree and the spectral gap of the resulting graph. We use the new product to give a fully-explicit combinatorial construction of D-regular graphs having spectral gap 1-D^{-1/2 + o(1)}.

REFERENCES

• 1: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 2: A. Lubotzky, Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.630, October 14-17, 2001
• 3: N. Alon and V. Milman.1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory. Series B, 38(1):73--88, 1985.
• 4: Yonatan Bilu , Nathan Linial, Lifts, Discrepancy and Nearly Optimal Spectral Gap, Combinatorica, v.26 n.5, p.495-519, October 2006 [doi>10.1007/s00493-006-0029-7]
• 5: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 6: J. Dodziuk. Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc., 284(2):787--794, 1984.
• 7: J. Friedman. A proof of Alon's second eigenvalue conjecture. Memoirs of the AMS, to appear.
• 8: O. Gabber and Z. Galil. Explicit Constructions of Linear-Sized Superconcentrators. Journal of Computer and System Sciences, 22(3):407--420, 1981.
• 9: S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, 43(4):439--561, 2006.
• 10: S. Janson, T. ÃLuczak, and A. Rucifinski. Random graphs. John Wiley New York, 2000.
• 11: Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
• 12: Nabil Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM (JACM), v.42 n.5, p.1091-1106, Sept. 1995 [doi>10.1145/210118.210136]
• 13: A. Lubotzky, R. Philips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261--277, 1988.
• 14: G. A. Margulis. Explicit constructions of expanders. Problemy Peredaci Informacii, 9(4):71--80, 1973.
• 15: G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51--60, 1988.
• 16: Roy Meshulam , Avi Wigderson, Expanders In Group Algebras, Combinatorica, v.24 n.4, p.659-680, September 2004 [doi>10.1007/s00493-004-0040-9]
• 17: Moshe Morgenstern, Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q, Journal of Combinatorial Theory Series B, v.62 n.1, p.44-62, Sept. 1994 [doi>10.1006/jctb.1994.1054]
• 18: 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]
• 19: M. Pinsker. On the complexity of a concentrator. In 7th Internat. Teletra±c Confer., pages 318/1--318/4, 1973.
• 20: Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060647]
• 21: O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, 155(1):157--187, 2002.
• 22: E. Rozenman, A. Shalev, and A. Wigderson. Iterative construction of cayley expander graphs. Theory of Computing, 2(5):91--120, 2006.
• 23: E. Rozenman and S. Vadhan. Derandomized squaring of graphs. In Proceedings of the 7th RANDOM, pages 436--447, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory

Keywords:
expander graphs, zig-zag product