An Elementary Construction of Constant-Degree Expanders
From MaRDI portal
Publication:3545900
DOI10.1017/S0963548307008851zbMATH Open1194.05021OpenAlexW2132890668MaRDI QIDQ3545900FDOQ3545900
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
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Vertex degrees (05C07)
Cites Work
- Eigenvalues and expanders
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Expander graphs and their applications
- Lifts, discrepancy and nearly optimal spectral gap
- Ramanujan graphs
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Random Cayley graphs and expanders
- Explicit constructions of linear-sized superconcentrators
- Recursive construction for 3-regular expanders
Cited In (13)
- Explicit expanders of every degree and size
- On Laplacians of random complexes
- Title not available (Why is that?)
- A spanner for the day after
- Balanced Hashing, Color Coding and Approximate Counting
- Layouts of Expander Graphs
- The eigenvalues of the graphs \(D(4,q)\)
- A global Poincaré inequality on graphs via a conical curvature-dimension condition
- Expander Construction in VNC1
- Nonlinear spectral calculus and super-expanders
- Efficient and Reliable Overlay Networks for Decentralized Federated Learning
- Expander construction in \(\mathrm{VNC}^1\)
- Bounds on the Twin-Width of Product Graphs
This page was built for publication: An Elementary Construction of Constant-Degree Expanders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545900)
