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

We study random $k$-lifts of large, butotherwise arbitrary graphs $G$. We prove that, with highprobability, all eigenvalues of the adjacency matrix of the liftthat are not eigenvalues of $G$ are of the order of$\sqrt{{\Delta_G} \ln(kn)}$, where ${\Delta_G}$ is the maximumdegree of $G$. Similarly, and also with high probability, the “new”eigenvalues of the normalized Laplacian of $G^{(k)}$ are all in aninterval oflength $O(\sqrt{\ln(nk)/\delta_G})$ around $1$, where$\delta_G$ is the minimum degree of $G$.

We also prove that, from the point of view of spectra, there is verylittle difference between a random $k_1\,k_2\,\dots\,k_r$-lift of agraph and a random $k_1$-lift of a random $k_2$-lift of $\dots$ ofa random $k_r$-lift of the same graph.

The main proof tool is a concentration inequality for sums ofindependent random matrices which is of independentinterest.

Keywords

random lifts of graphs, graph spectrum

2010 Mathematics Subject Classification

05C80

Full Text (PDF format)

Published 1 January 2010