Small Families of Partially Shattering Permutations

Abstract We say that a family of permutations t -shatters a set if it induces at least t distinct permutations on that set. What is the minimum number $$f_k(n,t)$$ f k ( n , t ) of permutations of $$\{1, \dots , n\}$$ { 1 , ⋯ , n } that t -shatter all subsets of size k ? For $$t \le 2$$ t ≤ 2 , $$f_k(n,t) = \Theta (1)$$ f k ( n , t ) = Θ ( 1 ) . Spencer showed that $$f_k(n,t) = \Theta (\log \log n)$$ f k ( n , t ) = Θ ( log log n ) for $$3 \le t \le k$$ 3 ≤ t ≤ k and $$f_k(n,k!) = \Theta (\log n)$$ f k ( n , k ! ) = Θ ( log n ) . In 1996, Füredi asked whether partial shattering with permutations must always fall into one of these three regimes. Johnson and Wickes recently settled the case $$k = 3$$ k = 3 affirmatively and proved that $$f_k(n,t) = \Theta (\log n)$$ f k ( n , t ) = Θ ( log n ) for $$t > 2 (k-1)!$$