کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423569 | 1342419 | 2011 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Random induced subgraphs of Cayley graphs induced by transpositions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we study random induced subgraphs of Cayley graphs of the symmetric group induced by an arbitrary minimal generating set of transpositions. A random induced subgraph of this Cayley graph is obtained by selecting permutations with independent probability, λn. Our main result is that for any minimal generating set of transpositions, for probabilities λn=1+ϵnnâ1 where nâ13+δâ¤Ïµn<1 and δ>0, a random induced subgraph has a.s. a unique largest component of size (1+o(1))â x(ϵn)â 1+ϵnnâ1â n!. Here x(ϵn) is the survival probability of a Poisson branching process with parameter λ=1+ϵn.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 21, 6 November 2011, Pages 2496-2511
Journal: Discrete Mathematics - Volume 311, Issue 21, 6 November 2011, Pages 2496-2511
نویسندگان
Emma Yu Jin, Christian M. Reidys,