Tight products and graph expansion

DOI10.1002/jgt.20593zbMath1242.05230OpenAlexW1608662552MaRDI QIDQ2891052

Nathan Linial, Amit Daniely

Publication date: 13 June 2012

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20593

zbMATH Keywords

random graphsexpanderslifts of graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph operations (line graphs, products, etc.) (05C76)

Related Items (2)

A note on semi-coloring of graphs ⋮ The existence of semi-colorings in a graph

Cites Work

• Random graph coverings. I: General theory and graph connectivity
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• Eigenvalues and expanders
• Finite common coverings of pairs of regular graphs
• Finite common coverings of graphs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Relative expanders or weakly relatively Ramanujan graphs.
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• Random lifts of graphs: perfect matchings
• Word maps and spectra of random graph lifts
• Expander graphs and their applications
• The NP-Completeness of Edge-Coloring
• Random lifts of graphs: Independence and chromatic number
• Random Lifts of Graphs: Edge Expansion

This page was built for publication: Tight products and graph expansion