umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The thresholds for diameter 2 in random Cayley graphs
School of Computing and Mathematics, UCLan Cyprus, Pyla, Cyprus.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2014 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, no 2, p. 218-235Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
John Wiley & Sons, 2014. Vol. 45, no 2, p. 218-235
Keyword [en]
random graphs, Cayley graphs, diameter
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-92705DOI: 10.1002/rsa.20486ISI: 000340278700003OAI: oai:DiVA.org:umu-92705DiVA, id: diva2:742344
Available from: 2014-09-01 Created: 2014-09-01 Last updated: 2018-02-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Markström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Random structures & algorithms (Print)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 59 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf