Random graph coverings. I: General theory and graph connectivity

DOI10.1007/S004930200000zbMath0996.05105OpenAlexW1974893148MaRDI QIDQ700369

Alon Amit, Nathan Linial

Publication date: 20 October 2002

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004930200000

zbMATH Keywords

random graph coverings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Related Items (26)

Tight products and graph expansion ⋮ Ramanujan coverings of graphs ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS ⋮ Spectrum of random d‐regular graphs up to the edge ⋮ Statistics of finite degree covers of torus knot complements ⋮ Expander graphs and their applications ⋮ Random lifts of graphs are highly connected ⋮ Signatures, Lifts, and Eigenvalues of Graphs ⋮ Relative expanders or weakly relatively Ramanujan graphs. ⋮ Expansion of random graphs: new proofs, new results ⋮ Cops and robber on some families of oriented graphs ⋮ Universality and sharp matrix concentration inequalities ⋮ 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 ⋮ Empirical spectral measures of quantum graphs in the Benjamini-Schramm limit ⋮ \(L^p\) norms and support of eigenfunctions on graphs ⋮ The spectral norm of random lifts of matrices ⋮ The chromatic number of random lifts of ⋮ Measure preserving words are primitive ⋮ Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks ⋮ Eigenvalues of random lifts and polynomials of random permutation matrices ⋮ On cylindrical graph construction and its applications

This page was built for publication: Random graph coverings. I: General theory and graph connectivity