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 range of thresholds for diameter 2 in random Cayley graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2014 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 35, 141-154 p.Article 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. Given a family of groups (G(k)) and a c is an element of R+ we say that c is the threshold for diameter 2 for (G(k)) if for any epsilon > 0 with high probability Gamma is an element of g(G(k), p) has diameter greater than 2 if p <= root(c - epsilon)log n/n and diameter at most 2 if p >= root(c + epsilon)log n/n. In Christofides and Markstrom (in press) [5] we proved that if c is a threshold for diameter 2 for a family of groups (G(k)) then c is an element of [1/4, 2] and provided two families of groups with thresholds 1/4 and 2 respectively. In this paper we study the question of whether every c is an element of [1/4, 2] is the threshold for diameter 2 for some family of groups. Rather surprisingly it turns out that the answer to this question is negative. We show that every c is an element of [1/4, 4/3] is a threshold but a c is an element of (4/3, 2] is a threshold if and only if it is of the form 4n/(3n - 1) for some positive integer n. 

Place, publisher, year, edition, pages
2014. Vol. 35, 141-154 p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-82279DOI: 10.1016/j.ejc.2013.06.030ISI: 000324786900014OAI: oai:DiVA.org:umu-82279DiVA: diva2:697448
Conference
6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb), AUG 29-SEP 02, 2011, Budapest, HUNGARY
Available from: 2014-02-18 Created: 2013-10-29 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Markström, Klas

Search in DiVA

By author/editor
Markström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
European journal of combinatorics (Print)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 83 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