An Elementary Construction of Constant-Degree Expanders

DOI10.1017/S0963548307008851zbMath1194.05021OpenAlexW2132890668MaRDI 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

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex degrees (05C07)

Related Items (11)

A global Poincaré inequality on graphs via a conical curvature-dimension condition ⋮ Expander Construction in VNC1 ⋮ The eigenvalues of the graphs \(D(4,q)\) ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Efficient and Reliable Overlay Networks for Decentralized Federated Learning ⋮ A spanner for the day after ⋮ On eigenvalues of random complexes ⋮ Nonlinear spectral calculus and super-expanders ⋮ Layouts of Expander Graphs ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ Unnamed Item

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

This page was built for publication: An Elementary Construction of Constant-Degree Expanders