Random Lifts of Graphs: Edge Expansion

DOI10.1017/S0963548305007273zbMath1095.05034OpenAlexW2073849603MaRDI QIDQ5479027

Alon Amit, Nathan Linial

Publication date: 6 July 2006

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548305007273

zbMATH Keywords

regular graphsrandom structures

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (20)

Cutoff for random lifts of weighted graphs ⋮ Tight products and graph expansion ⋮ Random lifts of graphs: Independence and chromatic number ⋮ CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS ⋮ Low-distortion embeddings of graphs with large girth ⋮ Spectrum of random d‐regular graphs up to the edge ⋮ Expander graphs and their applications ⋮ Random lifts of graphs are highly connected ⋮ Cryptographic hash functions from sequences of lifted Paley graphs ⋮ Expansion of random graphs: new proofs, new results ⋮ Hamilton cycles in random lifts of graphs ⋮ On the Number of Perfect Matchings in Random Lifts ⋮ \(\delta\)-connectivity in random lifts of graphs ⋮ Hamilton cycles in random lifts of graphs ⋮ Spectra of lifted Ramanujan graphs ⋮ Word maps and spectra of random graph lifts ⋮ The spectral norm of random lifts of matrices ⋮ The chromatic number of random lifts of ⋮ Eigenvalues of random lifts and polynomials of random permutation matrices ⋮ Interlacing families. I: Bipartite Ramanujan graphs of all degrees

This page was built for publication: Random Lifts of Graphs: Edge Expansion