On the spread of random graphs

2009/02/06 by Addario-Berry, Louigi, Janson, Svante, McDiarmid, Colin
#60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.0902.1156

Abstract

The spread of a connected graph G was introduced by Alon, Boppana and Spencer (1998) 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.

Related

• On the probability that a random subtree is spanning
• A note on the width of sparse random graphs
• An alternative approach to large deviations for the almost-critical Erdős-Rényi random graph
• Evolution of a modified binomial random graph by agglomeration
• A large deviation principle for the Erdős-Rényi uniform random graph