On the Spread of Random Graphs. (13th June 2014)

• Record Type: Journal Article
• Authors: ADDARIO-BERRY, LOUIGI; JANSON, SVANTE; McDIARMID, COLIN
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 4(2014:Jul.)
• Page Start: 477
• Page End: 504
• Publication Date: 2014-06-13
• Subjects: 60C05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000248
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G) . We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n, d), for Erdős–Rényi random graphs Gn, p in the supercritical range p>1/n, and for a 'small world' model. For supercritical Gn, p, we show that if p=c/n with c >1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p=(1+o(1))/n . Further, we show that for d large, with high probability the spread of G(n, d) becomes arbitrarily close to that of the complete graph $\mathsf{K}_n$ .