On the spread of random graphs

Journal article

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 G_n,p in the supercritical range p>1/n, and for a ‘small world’ model. For supercritical G_n,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 K_n

Authors: McDiarmid, C; Addario-Berry, L; Janson, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics Probability and Computing
• Volume: 23
• Issue: 4
• Pages: 477-504
• Publication date: 2014-06-13
• Acceptance date: 2013-07-16
• DOI: 10.1017/S0963548314000248
• EISSN: 1469-2163
• ISSN: 0963-5483
• Keywords: SBTMR