A note on scrambling permutations

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