A note on scrambling permutations

Abstract

A family F of permutations of [n] is completelyk-scrambling [Spencer,1972] if for every sequence <p₁, p₂,...,p_k > of k distinct elements of [n], there is a permutation π ∈ F with π(p₁) < π(p₂) < ,..,< π(p_k). We show that the size of the smallest completely k-scrambling family of permutations of [n] is at least 1+(2/log₂e)(n/2n−k+1)(k+1)log₂(n-k+2). This improves the previous best lower bound, due to Füredi 1996, by a factor of approximately 2/log₂e.