Umeå universitets logga

umu.sePublikationer
Ä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
The thresholds for diameter 2 in random Cayley graphs
School of Computing and Mathematics, UCLan Cyprus, Pyla, Cyprus.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2014 (Engelska)Ingår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, nr 2, s. 218-235Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Given a group G, the model G(G,p) denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any epsilon>0 and any family of groups G(k) of order n(k) for which nk, a graph kG(Gk,p) with high probability has diameter at most 2 if p(2+epsilon)lognknk and with high probability has diameter greater than 2 if p(14+epsilon)lognknk. We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erds-Renyi random graphs.

Ort, förlag, år, upplaga, sidor
John Wiley & Sons, 2014. Vol. 45, nr 2, s. 218-235
Nyckelord [en]
random graphs, Cayley graphs, diameter
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-92705DOI: 10.1002/rsa.20486ISI: 000340278700003Scopus ID: 2-s2.0-84905002071OAI: oai:DiVA.org:umu-92705DiVA, id: diva2:742344
Tillgänglig från: 2014-09-01 Skapad: 2014-09-01 Senast uppdaterad: 2023-03-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Markström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Markström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Random structures & algorithms (Print)
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 311 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