An Elementary Construction of Constant-Degree Expanders

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

Mathematics Subject Classification ID

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