On the Spread of Random Graphs. (13th June 2014) - ADDARIO-BERRY, LOUIGI; JANSON, SVANTE; McDIARMID, COLIN
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 K_n .