An Elementary Construction of Constant-Degree Expanders
From MaRDI portal
Publication:3545900
DOI10.1017/S0963548307008851zbMath1194.05021MaRDI QIDQ3545900
Noga Alon, Asaf Shapira, Oded Schwartz
Publication date: 11 December 2008
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C07: Vertex degrees
Related Items
On eigenvalues of random complexes, Nonlinear spectral calculus and super-expanders, The eigenvalues of the graphs \(D(4,q)\), Layouts of Expander Graphs, Balanced Hashing, Color Coding and Approximate Counting
Cites Work
- Lifts, discrepancy and nearly optimal spectral gap
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Ramanujan graphs
- Eigenvalues and expanders
- Explicit constructions of linear-sized superconcentrators
- Recursive construction for 3-regular expanders
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Expander graphs and their applications
- Random Cayley graphs and expanders
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks