A combinatorial construction of almost-Ramanujan graphs using the zig-zag product

MaRDI QIDQ3549716zbMATH OpenFDO

Authors Avraham Ben-Aroya, Amnon Ta-Shma

Publication date 5 January 2009

zbMATH Keywords

spectral gapexpander graphsgraph productzig-zag productlarge graphsmall graphD-regular graphs

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• On Construction of Almost-Ramanujan Graphs
• ON CONSTRUCTION OF ALMOST-RAMANUJAN GRAPHS
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Almost-Ramanujan graphs and prime gaps

Cited in

(11)

• Combinatorial algorithms for distributed graph coloring
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• On Construction of Almost-Ramanujan Graphs
• Combinatorial algorithms for distributed graph coloring
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Almost-Ramanujan graphs and prime gaps
• Pseudorandom linear codes are list-decodable to capacity
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• A generalization of the zig-zag graph product by means of the sandwich product
• When can an expander code correct (n) errors in O(n) time?
• ON CONSTRUCTION OF ALMOST-RAMANUJAN GRAPHS

This page was built for publication: A combinatorial construction of almost-Ramanujan graphs using the zig-zag product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549716)