Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the Spread of Random Graphs
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen.
2014 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 23, nr 4, s. 477-504Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

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 Erdos-Renyi 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.

Ort, förlag, år, upplaga, sidor
2014. Vol. 23, nr 4, s. 477-504
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:uu:diva-229429DOI: 10.1017/S0963548314000248ISI: 000338350900001OAI: oai:DiVA.org:uu-229429DiVA, id: diva2:736795
Tillgänglig från: 2014-08-08 Skapad: 2014-08-07 Senast uppdaterad: 2017-12-05Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Janson, Svante
Av organisationen
Matematiska institutionen
I samma tidskrift
Combinatorics, probability & computing
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 516 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf