Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T01:01:37.247Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Laplacian Eigenvalues of Gn,p

Published online by Cambridge University Press:  01 November 2007

AMIN COJA-OGHLAN
AMIN COJA-OGHLAN*
Affiliation:
Carnegie Mellon University, Department of Mathematical Sciences, Pittsburgh, PA 15213, USA (e-mail: coja@informatik.hu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We investigate the Laplacian eigenvalues of sparse random graphs Gnp. We show that in the case that the expected degree d = (n-1)p is bounded, the spectral gap of the normalized Laplacian $\LL(\gnp)$ is o(1). Nonetheless, w.h.p. G = Gnp has a large subgraph core(G) such that the spectral gap of $\LL(\core(G))$ is as large as 1-O (d−1/2). We derive similar results regarding the spectrum of the combinatorial Laplacian L(Gnp). The present paper complements the work of Chung, Lu and Vu [8] on the Laplacian spectra of random graphs with given expected degree sequences. Applied to Gnp, their results imply that in the ‘dense’ case d ≥ ln2n the spectral gap of $\LL(\gnp)$ is 1-O (d−1/2) w.h.p.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 6 , November 2007 , pp. 923 - 946
Copyright
Copyright © Cambridge University Press 2007

References

[1]Alon, N. (1998) Spectral techniques in graph algorithms. In Proc. 3rd LATIN, pp. 206–215.Google Scholar
[2]Alon, N. and Kahale, N. (1997) A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput. 26 1733–1748.CrossRefGoogle Scholar
[3]Alon, N., Krivelevich, M. and Sudakov, B. (1998) Finding a large hidden clique in a random graph. Random Struct. Alg. 13 457–466.3.0.CO;2-W>CrossRefGoogle Scholar
[4]Bauer, M. and Golinelli, O. (2001) Random incidence matrices: Moments of the spectral density. J. Statist. Phys. 103 301–337.CrossRefGoogle Scholar
[5]Bollobás, B. (2001) Random Graphs, 2nd edn, Springer.CrossRefGoogle Scholar
[6]Boppana, R. (1987) Eigenvalues and graph bisection: An average-case analysis. In Proc. 28th FOCS, pp. 280–285.Google Scholar
[7]Chung, F. R. K. (1997) Spectral Graph Theory, AMS.Google Scholar
[8]Chung, F. R. K., Lu, L. and Vu, V. (2003) The spectra of random graphs with given expected degrees. Internet Mathematics 1 257–275.CrossRefGoogle Scholar
[9]Coja-Oghlan, A. (2005) Spectral techniques, semidefinite programs, and random graphs. Habilitation thesis, Humboldt University, Berlin.Google Scholar
[10]Coja-Oghlan, A. (2006) A spectral heuristic for bisecting random graphs. Random Struct. Alg. 29 351–398.CrossRefGoogle Scholar
[11]Dasgupta, A., Hopcroft, J. E. and McSherry, F. (2004) Spectral partitioning of random graphs. In Proc. 45th FOCS, pp. 529–537.Google Scholar
[12]Donath, W. E. and Hoffman, A. J. (1973) Lower bounds for the partitioning of a graph. IBM J. Res. Develop. 17 420–425.CrossRefGoogle Scholar
[13]Feige, U. and Ofek, E. (2005) Spectral techniques applied to sparse random graphs. Random Struct. Alg. 27 251–275.CrossRefGoogle Scholar
[14]Friedman, J. (2003) A proof of Alon's second eigenvalue conjecture. In Proc. 35th STOC, pp. 720–724.Google Scholar
[15]Friedman, J., Kahn, J. and Szemerédi, E. (1989) On the second eigenvalue in random regular graphs. In Proc. 21st STOC, pp. 587–598.Google Scholar
[16]Füredi, Z. and Komloś, J. (1981) The eigenvalues of random symmetric matrices. Combinatorica 1 233–241.CrossRefGoogle Scholar
[17]Golub, G. H. and van Loan, C. F. (1996) Matrix Computations, 3rd edn, Johns Hopkins University Press.Google Scholar
[18]Guattery, S. and Miller, G. L. (1998) On the quality of spectral separators. SIAM J. Matrix Anal. Appl. 19 701–719.CrossRefGoogle Scholar
[19]Janson, S. (2005) The first eigenvalue of random graphs. Combin. Probab. Comput. 14 815–828.CrossRefGoogle Scholar
[20]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[21]Khorunzhiy, O., Kirsch, W. and Müller, P. (2005) Lifshits tails for spectra of Erdos–Renyi random graphs. Annals of applied probability 16 (2006) 295–309. Preprint: arXiv:math-ph/0502054 v1.Google Scholar
[22]Krivelevich, M. and Sudakov, B. (2003) The largest eigenvalue of sparse random graphs. Combin. Probab. Comput. 12 61–72.CrossRefGoogle Scholar
[23]Pothen, A., Simon, H. D. and Liou, K.-P. (1990) Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11 430–452.CrossRefGoogle Scholar
[24]Schloegel, K., Karypis, G. and Kumar, V. (2000) Graph partitioning for high performance scientific simulations. In CRPC Parallel Computation Handbook (Dongarra, J., Foster, I., Fox, G., Kennedy, K. and White, A., eds), Morgan-Kaufmann.Google Scholar
[25]Vu, V. (2005) Spectral norm of random matrices. In Proc. 37th STOC, pp. 423–430.Google Scholar
[26]Wigner, E. P. (1958) On the distribution of the roots of certain symmetric matrices. Ann. of Math. 67 325–327.CrossRefGoogle Scholar