An Elementary Construction of Constant-Degree Expanders

DOI10.1017/S0963548307008851MaRDI QIDQ3545900zbMATH OpenOpenAlexFDO

Authors Noga Alon, Oded Schwartz, Asaf Shapira

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

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

Recommendations

• An elementary construction of constant-degree expanders
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Explicit constructions of asymptotic families of constant degree expander graphs from AG codes
• Expander graphs and their applications
• Local expanders

Cites work

• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Eigenvalues and expanders
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• Explicit constructions of linear-sized superconcentrators
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Lifts, discrepancy and nearly optimal spectral gap
• Ramanujan graphs
• Random Cayley graphs and expanders
• Recursive construction for 3-regular expanders

Cited in

(14)

• Expander construction in \(\mathrm{VNC}^1\)
• Explicit expanders of every degree and size
• Expander construction in \(\mathsf{VNC}^1\)
• A global Poincaré inequality on graphs via a conical curvature-dimension condition
• Local expanders
• A spanner for the day after
• Efficient and reliable overlay networks for decentralized federated learning
• Balanced hashing, color coding and approximate counting
• Nonlinear spectral calculus and super-expanders
• Deterministic approximation of random walks in small space
• An elementary construction of constant-degree expanders
• The eigenvalues of the graphs \(D(4,q)\)
• Bounds on the Twin-Width of Product Graphs
• Layouts of Expander 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)