On the Minimum Number of Completely 3-Scrambling Permutations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

On the Minimum Number of Completely 3-Scrambling Permutations

Résumé

A family $\mathcal{P} = \{\pi_1, \ldots , \pi_q\}$ of permutations of $[n]=\{1,\ldots,n\}$ is $\textit{completely}$ $k$-$\textit{scrambling}$ [Spencer, 1972; Füredi, 1996] if for any distinct $k$ points $x_1,\ldots,x_k \in [n]$, permutations $\pi_i$'s in $\mathcal{P}$ produce all $k!$ possible orders on $\pi_i (x_1),\ldots, \pi_i(x_k)$. Let $N^{\ast}(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. $\frac{2}{ \log _2e} \log_2 n \leq N^{\ast}(n,3) \leq 2\log_2n + (1+o(1)) \log_2 \log _2n$. We also prove the existence of $\lim_{n \to \infty} N^{\ast}(n,3) / \log_2 n = c_3$. 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.
Fichier principal
Vignette du fichier
dmAE0168.pdf (151 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184432 , version 1 (14-08-2015)

Identifiants

Citer

Jun Tarui. On the Minimum Number of Completely 3-Scrambling Permutations. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.351-356, ⟨10.46298/dmtcs.3443⟩. ⟨hal-01184432⟩

Collections

TDS-MACS
38 Consultations
546 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More