Christofides, Demetres and Markstrom, Klas (2014) The range of thresholds for diameter 2 in random Cayley graphs. European Journal of Combinatorics, 35 . pp. 141154. ISSN 01956698

PDF (Author Accepted Manuscript)
 Accepted Version
Available under License Creative Commons Attribution Noncommercial No Derivatives. 347kB 
Official URL: http://dx.doi.org/10.1016/j.ejc.2013.06.030
Abstract
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 \in \mathbb{R}_+$ we say that c is the threshold for diameter 2 for (G_k) if for any ε > 0 with high probability $\Gamma \in \mathcal{G}(G_k,p)$ has diameter greater than 2 if $p \leqslant \sqrt{(c  \eps)\frac{\log{n}}{n}}$ and diameter at most 2 if $p \geqslant \sqrt{(c + \eps)\frac{\log{n}}{n}}$. In [5] we proved that if c is a threshold for diameter 2 for a family of groups (G_k) then $c \in [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 \in [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 \in [1/4,4/3]$ is a threshold but a $c \in (4/3,2]$ is a threshold if and only if it is of the form 4n/(3n1) for some positive integer n.
Repository Staff Only: item control page