کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424185 | 1632784 | 2014 | 14 صفحه PDF | دانلود رایگان |
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 (Gk) and a câR+ we say that c is the threshold for diameter 2 for (Gk) if for any ε>0 with high probability ÎâG(Gk,p) has diameter greater than 2 if p⩽(câε)lognn and diameter at most 2 if p⩾(c+ε)lognn. In Christofides and Markström (in press) [5] we proved that if c is a threshold for diameter 2 for a family of groups (Gk) then câ[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â[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â[1/4,4/3] is a threshold but a câ(4/3,2] is a threshold if and only if it is of the form 4n/(3nâ1) for some positive integer n.
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 141-154