Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

Jun Tarui - On the Minimum Number of Completely 3-Scrambling Permutations

dmtcs:3443 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3443
On the Minimum Number of Completely 3-Scrambling PermutationsConference paper

Authors: Jun Tarui 1

  • 1 Department of Information and Communication Engineering [Tokyo]

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. 2log2elog2nN(n,3)2log2n+(1+o(1))log2log2n. We also prove the existence of lim. Determining the value c_3 and proving the existence of \lim_{n \to \infty} N^{\ast}(n,k) / \log_2 n = c_k for k \geq 4 remain open.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: completely scrambling permutations,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

9 Documents citing this article

Consultation statistics

This page has been seen 218 times.
This article's PDF has been downloaded 234 times.