کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650592 1342494 2008 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the minimum number of completely 3-scrambling permutations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the minimum number of completely 3-scrambling permutations
چکیده انگلیسی

A family P={π1,…,πq}P={π1,…,πq} of permutations of [n]={1,…,n}[n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k   points x1,…,xk∈[n]x1,…,xk∈[n], permutations πiπi's in PP produce all k!k! possible orders on πi(x1),…,πi(xk)πi(x1),…,πi(xk). Let N*(n,k)N*(n,k) be the minimum size of such a family. This paper focuses on the case k=3k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison. 2log2elog2n⩽N*(n,3)⩽2log2n+(1+o(1))log2log2n.We also prove the existence of limn→∞N*(n,3)/log2n=c3. Determining the value c3c3 and proving the existence of limn→∞N*(n,k)/log2n=ck for k⩾4k⩾4 remain open.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 8, 28 April 2008, Pages 1350–1354
نویسندگان
,