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

(15)

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

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)