skip to main content
10.1145/1374376.1374424acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article

A combinatorial construction of almost-ramanujan graphs using the zig-zag product

Published: 17 May 2008 Publication History

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. Eigenvalues and expanders. Combinatorica, 6(2):83--96, 1986.
[2]
N. Alon, A. Lubotzky, and A. Wigderson. Semi-direct product in groups and zig-zag product in graphs: connections and applications. In Proceedings of the 42nd FOCS, pages 630--637, 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]
Y. Bilu and N. Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495--519, 2006.
[5]
M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson. Randomness conductors and constant-degree expansion beyond the degree / 2 barrier. In Proceedings of the 34th STOC, pages 659--668, 2002.
[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]
S. Jimbo and A. Maruoka. Expanders obtained from affine transformations. Combinatorica, 7(4):343--355, 1987.
[12]
N. Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42(5):1091--1106, 1995.
[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]
R. Meshulam and A. Wigderson. Expanders in group algebras. Combinatorica, 24(4):659--680, 2004.
[17]
M. Morgenstern. Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory. Series B, 62(1):44--62, 1994.
[18]
A. Nilli. On the second eigenvalue of a graph. Discrete Mathematics, 91(2):207--210, 1991.
[19]
M. Pinsker. On the complexity of a concentrator. In 7th Internat. Teletra±c Confer., pages 318/1--318/4, 1973.
[20]
O. Reingold. Undirected st-connectivity in log-space. In Proceedings of the 37th STOC, pages 376--385, 2005.
[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.

Cited By

View all
  • (2023)One stride ahead Advancements in Dispersed Graph Coloring2023 International Conference for Advancement in Technology (ICONAT)10.1109/ICONAT57137.2023.10080064(1-3)Online publication date: 24-Jan-2023
  • (2022)Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00043(378-388)Online publication date: Oct-2022
  • (2015)Almost-Ramanujan graphs and prime gapsEuropean Journal of Combinatorics10.1016/j.ejc.2014.09.00143:C(204-209)Online publication date: 1-Jan-2015
  • Show More Cited By

Index Terms

  1. A combinatorial construction of almost-ramanujan graphs using the zig-zag product

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing
      May 2008
      712 pages
      ISBN:9781605580470
      DOI:10.1145/1374376
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 17 May 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. expander graphs
      2. zig-zag product

      Qualifiers

      • Research-article

      Conference

      STOC '08
      Sponsor:
      STOC '08: Symposium on Theory of Computing
      May 17 - 20, 2008
      British Columbia, Victoria, Canada

      Acceptance Rates

      STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;
      Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

      Upcoming Conference

      STOC '25
      57th Annual ACM Symposium on Theory of Computing (STOC 2025)
      June 23 - 27, 2025
      Prague , Czech Republic

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)8
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 22 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)One stride ahead Advancements in Dispersed Graph Coloring2023 International Conference for Advancement in Technology (ICONAT)10.1109/ICONAT57137.2023.10080064(1-3)Online publication date: 24-Jan-2023
      • (2022)Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00043(378-388)Online publication date: Oct-2022
      • (2015)Almost-Ramanujan graphs and prime gapsEuropean Journal of Combinatorics10.1016/j.ejc.2014.09.00143:C(204-209)Online publication date: 1-Jan-2015
      • (2014)Combinatorial algorithms for distributed graph coloringDistributed Computing10.1007/s00446-013-0203-227:2(79-93)Online publication date: 1-Apr-2014
      • (2012)A key-distribution mechanism for wireless sensor networks using Zig-Zag productInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2012.04928011:1(1-10)Online publication date: 1-Sep-2012
      • (2011)Combinatorial algorithms for distributed graph coloringProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075036(66-81)Online publication date: 20-Sep-2011
      • (2011)Combinatorial Algorithms for Distributed Graph ColoringDistributed Computing10.1007/978-3-642-24100-0_5(66-81)Online publication date: 2011
      • (2009)On the connectivity of key-distribution strategies in wireless sensor networksProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812301(5554-5559)Online publication date: 30-Nov-2009
      • (2009)On the Connectivity of Key-Distribution Strategies in Wireless Sensor NetworksGLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference10.1109/GLOCOM.2009.5425590(1-6)Online publication date: Nov-2009
      • (2009)On Construction of Almost-Ramanujan GraphsCombinatorial Optimization and Applications10.1007/978-3-642-02026-1_18(197-207)Online publication date: 2009
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media