The thresholds for diameter 2 in random Cayley graphs1. Issue 2 (5th March 2013) - Christofides, Demetres; Markström, Klas
ABSTRACT Given a group G, the model <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p0nfm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(G, p)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p0n7h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ε>0</alternatives> and any family of groups Gk of order nk for which <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p0n81" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />nk→∞</alternatives>, a graph <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p0pdk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Γk∈G(Gk, p)</alternatives> with high probability has diameter at most 2 if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p0pbj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≥(2+ε)lognknk</alternatives> and with high probability has diameter greater than 2 if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4p0p91" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≤(14+ε)lognknk</alternatives>. 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 Erdős‐Renyi random graphs. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 218–235, 2014