Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the Minimum Numbe ...
Conference paper

On the Minimum Number of Completely 3-Scrambling Permutations

Jun Tarui (1)
(1) Department of Information and Communication Engineering [Tokyo]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3443
License
https://about.hal.science/hal-authorisation-v1
Indicators
570
Views
560
Downloads

On the Minimum Number of Completely 3-Scrambling Permutations

Jun Tarui (1)
(1) Department of Information and Communication Engineering [Tokyo]
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • completely scrambling permutations
Cited by

Source: OpenCitations

  • Shattering k-sets with Permutations

    Order

    Authors : J. Robert Johnson, Belinda Wickes

    Journal reference : Volume 41, 2023, pp. 419-436

    DOI : 10.1007/s11083-023-09637-7

  • A selective encryption scheme for H.264 video based on permutation code and dynamic keys

    2012 International Conference on Computer Communication and Informatics

    Authors : L. M. Varalakshmi, V. Bharathi, V. Florence Sudha

    Journal reference : Volume , 2012, pp. 1-5

    DOI : 10.1109/iccci.2012.6158788

  • Perfect sequence covering arrays

    Designs Codes and Cryptography

    Authors : Raphael Yuster ORCID

    Journal reference : Volume 88, 2019, pp. 585-593

    DOI : 10.1007/s10623-019-00698-7

  • Perfect and nearly perfect separation dimension of complete and random graphs

    arXiv (Cornell University)

    Authors : Raphael Yuster ORCID

    Journal reference : Volume 29, 2021, pp. 786-805

    DOI : 10.1002/jcd.21802

  • New upper bounds for sequence Covering Arrays using a 3-stage approach

    Expert Systems with Applications

    Authors : Jose Torres-Jimenez ORCID, Daniel Osvaldo Ramirez-Acuna, Brenda Acevedo-Juárez ORCID, Himer Avila-George ORCID

    Journal reference : Volume 207, 2022, pp. 118022

    DOI : 10.1016/j.eswa.2022.118022

  • A New Algorithm for Using Dynamic Keys Encryption Video Information

    2009 Second International Workshop on Computer Science and Engineering

    Authors : Shaosheng Guo, Youxin Meng, Wei Zhang ORCID

    Journal reference : Volume 35, 2009, pp. 542-545

    DOI : 10.1109/wcse.2009.871

  • Sequence Covering Arrays and Linear Extensions

    Lecture notes in computer science

    Authors : Patrick C. Murray, Charles J. Colbourn ORCID

    Journal reference : Volume , 2015, pp. 274-285

    DOI : 10.1007/978-3-319-19315-1_24

  • T-Way Strategy for Sequence Input Interaction Test Case Generation Adopting Fish Swarm Algorithm

    Lecture notes in electrical engineering

    Authors : Mostafijur Rahman ORCID, Dalia Sultana, Sabira Khatun ORCID, Mohd Falfazli Mat Jusof ORCID, Syamimi Mardiah Shaharum ORCID, Nurhafizah Abu Talip Yusof ORCID, Khandker M. Qaiduzzaman, Md Hasibul Hasan ORCID, Md Mushfiqur Rahman ORCID, Md Anwar Hossen ORCID, Afsana Begum ORCID

    Journal reference : Volume , 2020, pp. 87-99

    DOI : 10.1007/978-981-15-2317-5_9

  • Combinatorial Test Sequence Generation Method Integrated with STPA

    International Journal of Software Engineering and Knowledge Engineering

    Authors : Heng Xu ORCID, Zhiqiu Huang ORCID, Chuanqi Tao ORCID, Jian Xie ORCID, Jun Hu ORCID

    Journal reference : Volume 36, 2025, pp. 403-429

    DOI : 10.1142/s021819402550072x

  • Sequence Covering Arrays

    DR-NTU (Nanyang Technological University)

    Authors : Yeow Meng Chee ORCID, Charles J. Colbourn ORCID, Daniel Horsley ORCID, Junling Zhou

    Journal reference : Volume 27, 2013, pp. 1844-1861

    DOI : 10.1137/120894099
Preview
Loading PDF preview...