DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

On the Minimum Number of Completely 3-Scrambling Permutations

Jun Tarui


A family P = {π1,…,πq} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, 1972; Füredi, 1996] if for any distinct k points x1,…,xk∈[n], permutations πi's in P produce all k! possible orders on πi(x1),…,πi(xk). Let N*(n,k) be the minimum size of such a family. This paper focuses on the case k=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. 2 / log2e log2 n ≤ N*(n,3) ≤2log2n + (1+o(1))log2log2n. We also prove the existence of limn→∞ N*(n,3) / log2 n = c3 . Determining the value c3 and proving the existence of limn→∞ N*(n,k) / log2 n = ck for k ≥4 remain open.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional