Expander Graphs - Both Local and Global

Let G=(V, E) be a finite graph. For vϵ V we denote by G_v the subgraph of G that is induced by v's neighbor set. We say that G is (a, b) -regular for a>b>0 integers, if G is a-regular and G v is b-regular for every vϵ V. Recent advances in PCP theory call for the construction of infinitely many (a, b) -regular expander graphs G that are expanders also locally. Namely, all the graphs {G v |vϵ V} should be expanders as well. While random regular graphs are expanders with high probability, they almost surely fail to expand locally. Here we construct two families of (a, b) -regular graphs that expand both locally and globally. We also analyze the possible local and global spectral gaps of (a, b) -regular graphs. In addition, we examine our constructions vis-a-vis properties which are considered characteristic of high-dimensional expanders.

Authors

• Michael Chapman
• Nati Linial
• Yuval Peled

Keywords

• Graph theory
• Eigenvalues and eigenfunctions
• Computer science
• Convergence
• Organizations
• Terminology
• Expander Graphs
• Almost Surely
• Local Disruption
• Regular Graphs
• Global Gap
• Finite Graph
• Eigenvalues
• Random Walk
• Tensor Product
• Considerable Body
• Simplicial Complex
• Local Expansion
• Simple Cycle
• Backward Step
• Multiset
• Lie Detection
• Expander-Graphs
• High-dimensional Combinatorics