EUVIMEDEUVIMED entdecken
Crossref

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

Roberto Imbuzeiro Oliveira

Journal of Combinatorics · 2010

DOI: 10.4310/joc.2010.v1.n3.a2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Combinatorics, 2010. Verfasst von Roberto Imbuzeiro Oliveira. Die Arbeit wurde bisher 6-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Oliveira, R. I. (2010). The spectrum of random $k$-lifts of large graphs (with possibly large $k$). Journal of Combinatorics. https://doi.org/10.4310/joc.2010.v1.n3.a2

Vancouver

Oliveira RI. The spectrum of random $k$-lifts of large graphs (with possibly large $k$). Journal of Combinatorics. 2010. doi:10.4310/joc.2010.v1.n3.a2

BibTeX
@article{Oliveira2010,
  author = {Oliveira, Roberto Imbuzeiro},
  title = {The spectrum of random $k$-lifts of large graphs (with possibly large $k$)},
  journal = {Journal of Combinatorics},
  year = {2010},
  doi = {10.4310/joc.2010.v1.n3.a2}
}
Kostenlos starten →