An Elementary Construction of Constant-Degree Expanders
From MaRDI portal
Publication:3545900
DOI10.1017/S0963548307008851zbMath1194.05021MaRDI QIDQ3545900
Oded Schwartz, Asaf Shapira, Noga Alon
Publication date: 11 December 2008
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548307008851
68R10: Graph theory (including graph drawing) in computer science
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C07: Vertex degrees
Related Items
Expander Construction in VNC1, Unnamed Item, Efficient and Reliable Overlay Networks for Decentralized Federated Learning, On eigenvalues of random complexes, A global Poincaré inequality on graphs via a conical curvature-dimension condition, Expander construction in \(\mathrm{VNC}^1\), A spanner for the day after, 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