On the spread of random graphs
<p style="text-align:justify;"> 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 distrib...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Journal article |
| Được phát hành: |
Cambridge University Press
2014
|
| _version_ | 1826298781472129024 |
|---|---|
| author | McDiarmid, C Addario-Berry, L Janson, S |
| author_facet | McDiarmid, C Addario-Berry, L Janson, S |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | <p style="text-align:justify;"> 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<sub>n,p</sub> in the supercritical range p>1/n, and for a ‘small world’ model. For supercritical G<sub>n,p</sub>, 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<sub>n</sub></p> |
| first_indexed | 2024-03-07T04:52:03Z |
| format | Journal article |
| id | oxford-uuid:d54f9c26-a514-4e11-b086-76e7d5ecfa2f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:52:03Z |
| publishDate | 2014 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:d54f9c26-a514-4e11-b086-76e7d5ecfa2f2022-03-27T08:24:57ZOn the spread of random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d54f9c26-a514-4e11-b086-76e7d5ecfa2fSymplectic Elements at OxfordCambridge University Press2014McDiarmid, CAddario-Berry, LJanson, S <p style="text-align:justify;"> 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<sub>n,p</sub> in the supercritical range p>1/n, and for a ‘small world’ model. For supercritical G<sub>n,p</sub>, 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<sub>n</sub></p> |
| spellingShingle | McDiarmid, C Addario-Berry, L Janson, S On the spread of random graphs |
| title | On the spread of random graphs |
| title_full | On the spread of random graphs |
| title_fullStr | On the spread of random graphs |
| title_full_unstemmed | On the spread of random graphs |
| title_short | On the spread of random graphs |
| title_sort | on the spread of random graphs |
| work_keys_str_mv | AT mcdiarmidc onthespreadofrandomgraphs AT addarioberryl onthespreadofrandomgraphs AT jansons onthespreadofrandomgraphs |