Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

Details Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

2009-11-03

arxiv.org/abs/0911.0600v2

Mathematics

Combinatorics

46 pages, submitted

Scientific paper

Consider any random graph model where potential edges appear independently, with possibly different probabilities, and assume that the minimum expected degree is omega(ln n). We prove that the adjacency matrix and the Laplacian of that random graph are concentrated around the corresponding matrices of the weighted graph whose edge weights are the probabilities in the random model. While this may seem surprising, we will see that this matrix concentration phenomenon is a generalization of known results about the Er\"{o}s-R\'{e}nyi model. In particular, we will argue that matrix concentration is implicit the theory of quasi-random graph properties. We present two main applications of the main result. In bond percolation over a graph G, we show that the Laplacian of the random subgraph is typically very close to the Laplacian of G. As a corollary, we improve upon a bound for the spectral gap due to Chung and Horn that was derived via much more complicated methods. In inhomogeneous random graphs, there are points X_1,...,X_n uniformly distributed on the interval [0,1] and each pair is connected with probability p kappa(X_i,X_j). We show that if \ln n/n<< p<< 1 and kappa is bounded, then the adjacency matrix of the random graph is close to an integral operator defined in terms of kappa. Our main proof tool is a new concentration inequality for matrix martingales that generalizes Freedman's inequality for the standard scalar setting.

Affiliated with

Also associated with

No associations

Rating

Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256728