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: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000248
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>The <italic>spread</italic> of a connected graph <italic>G</italic> 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 <italic>f</italic> on <italic>V(G)</italic> of the variance of <italic>f(X)</italic> when <italic>X</italic> is uniformly distributed on <italic>V(G)</italic>. We investigate the spread for certain models of sparse random graph, in particular for random regular graphs <italic>G(n, d)</italic>, for Erdős–Rényi random graphs <italic>G<sub>n, p</sub></italic> in the supercritical range <italic>p>1/n</italic>, and for a 'small world' model. For supercritical <italic>G<sub>n, p</sub></italic>, we show that if <italic>p=c/n</italic> with <italic>c</italic>>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 <italic>p=(1+o(1))/n</italic>. Further, we show that for <italic>d</italic> large, with high probability the spread of <italic>G(n, d)</italic> becomes arbitrarily close to that of the complete graph <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pghjm91rk7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathsf{K}_n$]]></tex-math></alternatives></inline-formula>.</p> </abstract>