Infinite families of regular expanders of arbitrary constant degree obtained via the modified zig-zag product

2009/05/23 by Cristina Ballantine, Matthew Horton, Ballantine, Cristina +1
Mathematics · #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C50

paper · pdf · doi:10.48550/arxiv.0905.3862

Paper withdrawn due to error in main theorem

openalex publication_date 2009/05/23 · arxiv created 2010/08/28 · arxiv updated 2010/08/31 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We generalize the zig-zag product construction to produce infinite families of regular graphs of any constant degree. We analyze the second largest eigenvalue of this new zig-zag product to show that the modified zig-zag product of good expanders is again a good expander (yet not Ramanujan).

Related

• High dimensional expansion using zig-zag product
• Generalized zig-zag products of regular digraphs and bounds on their spectral expansions
• On high-girth expander graphs with localized eigenvectors
• Expanding graphs, Ramanujan graphs, and 1-factor perturbations
• A note on the structure of expanders