×

Spectra of edge-independent random graphs. (English) Zbl 1295.05211

Summary: Let \(G\) be a random graph on the vertex set \(\{1,2,\ldots, n\}\) such that edges in \(G\) are determined by independent random indicator variables, while the probabilities \(p_{ij}\) for \(\{i,j\}\) being an edge in \(G\) are not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of \(G\) are recently studied by R. Oliveira [“Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges”, Preprint, arXiv:0911.0600] and F. Chung and M. Radcliffe [Electron. J. Comb. 18, No. 1, Research Paper P215, 14 p. (2011; Zbl 1229.05248)]. Let \(A\) be the adjacency matrix of \(G, \bar A=\text{ E}(A)\), and \(\Delta\) be the maximum expected degree of \(G\). Oliveira [loc. cit.] first proved that asymptotically almost surely \(\|A-\bar A\|=O(\sqrt{\Delta \ln n})\) provided \(\Delta\geq C \ln n\) for some constant \(C\). Chung-Radcliffe [loc. cit.] improved the hidden constant in the error term using a new Chernoff-type inequality for random matrices. Here we prove that asymptotically almost surely \(\|A-\bar A\|\leq (2+o(1))\sqrt{\Delta}\) with a slightly stronger condition \(\Delta\gg \ln^4 n\). For the Laplacian matrix \(L\) of \(G\), Oliveira [loc. cit.] and Chung-Radcliffe [loc. cit.] proved similar results \(\|L-\bar L\|=O(\sqrt{\ln n}/\sqrt{\delta})\) provided the minimum expected degree \(\delta\geq C' \ln n\) for some constant \(C'\); we also improve their results by removing the \(\sqrt{\ln n}\) multiplicative factor from the error term under some mild conditions. Our results naturally apply to the classical Erdős-Rényi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
15A18 Eigenvalues, singular values, and eigenvectors

Citations:

Zbl 1229.05248

References:

[1] N. Alon, M. Krivelevich, and V. H. Vu, Concentration of eigenvalues of random matrices, Israel Math. J., 131 (2002), 259-267. · Zbl 1014.15016
[2] H. Chernoff, A note on an inequality involving the normal distribution, Ann. Probab., 9 (1981), 533-535. · Zbl 0457.60014
[3] F. Chung, Spectral graph theory, AMS publications, 1997. · Zbl 0867.05046
[4] F. Chung, L. Lu, and V. H. Vu, Eigenvalues of random power law graphs, Ann. Comb., 7 (2003), 21-33. · Zbl 1017.05093
[5] F. Chung, L. Lu, and V. H. Vu, Spectra of random graphs with given expected degrees, Proc. Natl. Acad. Sci. USA, 100(11) (2003), 6313-6318. · Zbl 1064.05138
[6] F. Chung and M. Radcliffe, On the spectra of general random graphs, Electron. J. Combin., 18(1) (2011), P215. the electronic journal of combinatorics 20(4) (2013), #P2717 · Zbl 1229.05248
[7] A. Coja-Oghlan, On the Laplacian eigenvalues of G(n, p), Combin. Probab. Comput., 16(6) (2007), 923-946. · Zbl 1127.05062
[8] A. Coja-Oghlan and A. Lanka, The spectral gap of random graphs with given expected degrees, Electron. J. Combin., 16 (2009), R138. · Zbl 1187.05048
[9] D. M. Cvetkovi´c, M. Doob, and H. Sachs, Spectra of Graphs, Theory and Applications, Academic Press, 1980. · Zbl 0458.05042
[10] X. Ding and T. Jiang, Spectral distributions of adjacency and Laplacian matrices of random graphs, Ann. Appl. Probab., 20(6) (2010), 2086-2117. · Zbl 1231.05236
[11] U. Feige and E. Ofek, Spectral techniques applied to sparse random graphs, Random Structures Algorithms, 27(2) (2005), 251-275. · Zbl 1076.05073
[12] J. N. Franklin, Matrix Theory, Prentice-Hall, 1968. · Zbl 0174.31501
[13] J. Friedman, J. Kahn, and E. Szemer´edi, On the second eigenvalue in random regular graphs, in Proc. 21st ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1989, 587-598.
[14] J. Friedman, On the second eigenvalue and random walks in random d-regular graphs, Combinatorica, 11(4) (1991), 331-362. · Zbl 0760.05078
[15] J. Friedman, A Proof of Alon’s Second Eigenvalue Conjecture and Related Problem, Memoirs of the American Mathematical Society 2008, 100 pp. · Zbl 1177.05070
[16] Z. F¨uredi and J. Koml´os. The eigenvalues of random symmetric matrices,Combinatorica, 1(3) 1981, 233-241. · Zbl 0494.15010
[17] M. Krivelevich and B. Sudakov, The largest eigenvalue of sparse random graphs, Combin. Probab. Comput., 12 (2003), 61-72. · Zbl 1012.05109
[18] R. Oliveira, Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges, [math.CO].
[19] J. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12(4) 2012, 389-434. · Zbl 1259.60008
[20] V. H. Vu, Spectral norm of random matrices, Combinatorica, 27 (6) (2007), 721-736. · Zbl 1164.05066
[21] E. P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. Math., 67 (1958), 325-327. · Zbl 0085.13203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.