Premium
A note on scrambling permutations
Author(s) -
Radhakrishnan Jaikumar
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10082
Subject(s) - scrambling , permutation (music) , combinatorics , sequence (biology) , mathematics , struct , random permutation , upper and lower bounds , physics , computer science , algorithm , block (permutation group theory) , genetics , biology , mathematical analysis , acoustics , programming language
A family ℱ of permutations of [ n ] is completely k ‐ scrambling [Spencer,1972] if for every sequence 〈 p 1 , p 2 , …, p k 〉 of k distinct elements of [ n ], there is a permutation π ∈ ℱ with π( p 1 ) < π( p 2 ) < … < π( p k ). We show that the size of the smallest completely k ‐scrambling family of permutations of [ n ] is at least\documentclass{article}\pagestyle{empty}\begin{document}\begin{displaymath} 1 + \left(\frac{2}{\mathrm{log}_2\,e}\right)\!\left(\frac{n}{2 n - k + 1}\right)\!(k - 1)! \; \mathrm{log}_2 (n - k + 2)\end{displaymath}\end{document} This improves the previous best lower bound, due to Füredi 1996, by a factor of approximately 2/log 2 e . © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 435–439, 2003