کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424185 1632784 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The range of thresholds for diameter 2 in random Cayley graphs
ترجمه فارسی عنوان
دامنه آستانه برای قطر 2 در نمودارهای کایلی تصادفی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 141-154
نویسندگان
, ,