The spectrum of random k-lifts of large graphs (with possibly large k)

DOI10.4310/JOC.2010.V1.N3.A2zbMATH Open1244.05147arXiv0911.4741MaRDI QIDQ547863FDOQ547863

Authors: Roberto I. Oliveira 

Publication date: 27 June 2011

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: We study random k-lifts of large, but otherwise arbitrary graphs G. We prove that, with high probability, all eigenvalues of the adjacency matrix of the lift that are not eigenvalues of G are of the order (D ln (kn))^{1/2}, where D is the maximum degree of G. Similarly, and also with high probability, the "new" eigenvalues of the Laplacian of the lift are all in an interval of length (ln (nk)/d)^{1/2} around 1, where d is the minimum degree of G. We also prove that, from the point of view of Spectral Graph Theory, there is very little difference between a random k_1k_2 ... k_r-lift of a graph and a random k_1-lift of a random k_2-lift of ... of a random k_r-lift of the same graph. The main proof tool is a concentration inequality for sums of random matrices that was recently introduced by the author.

Full work available at URL: https://arxiv.org/abs/0911.4741

Recommendations

• The spectral norm of random lifts of matrices
• Spectra of lifted Ramanujan graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Word maps and spectra of random graph lifts
• Eigenvalues of random lifts and polynomials of random permutation matrices

zbMATH Keywords

graph spectrumrandom lifts of graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graph operations (line graphs, products, etc.) (05C76)

Cited In (14)

• Signatures, lifts, and eigenvalues of graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Spectra and eigenspaces of arbitrary lifts of graphs
• Word maps and spectra of random graph lifts
• The spectra of multiplicative attribute graphs
• Time-uniform Chernoff bounds via nonnegative supermartingales
• The spectral norm of random lifts of matrices
• On the expansion of group-based lifts
• Spectra of lifted Ramanujan graphs
• The expected norm of a sum of independent random matrices: an elementary approach
• T-product tensors. II: Tail bounds for sums of random T-product tensors
• On the expansion of group-based lifts
• On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

This page was built for publication: The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)

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