Random graph coverings. I: General theory and graph connectivity

DOI10.1007/S004930200000MaRDI QIDQ700369zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Random graphs and covering graphs of posets
• Random lifts of graphs
• Random lifts of graphs are highly connected
• On the connectivity of graphs generated by a sum of random mappings
• Near perfect coverings in graphs and hypergraphs

Cited in

(30)

• Eigenvalues of random lifts and polynomials of random permutation matrices
• Universality and sharp matrix concentration inequalities
• On Cover Graphs and Dependent Arcs in Acyclic Orientations
• Signatures, lifts, and eigenvalues of graphs
• Measure preserving words are primitive
• Random graphs and covering graphs of posets
• Random lifts of graphs are highly connected
• Tight products and graph expansion
• Relative expanders or weakly relatively Ramanujan graphs.
• Spectrum of random d‐regular graphs up to the edge
• Hamilton cycles in random lifts of graphs
• Hamilton cycles in random lifts of graphs
• Expansion of random graphs: new proofs, new results
• Empirical spectral measures of quantum graphs in the Benjamini-Schramm limit
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Ramanujan coverings of graphs
• On cylindrical graph construction and its applications
• Expander graphs and their applications
• Minimum vertex cover in generalized random graphs with power law degree distribution
• On the number of perfect matchings in random lifts
• The spectral norm of random lifts of matrices
• \(\delta\)-connectivity in random lifts of graphs
• Average covering number for some graphs
• \(L^p\) norms and support of eigenfunctions on graphs
• Cops and robber on some families of oriented graphs
• The chromatic number of random lifts of \(K_5\setminus e\)
• Spectra of lifted Ramanujan graphs
• Cutoff at the entropic time for random walks on covered expander graphs
• Statistics of finite degree covers of torus knot complements
• Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks

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

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