Small Families of Partially Shattering Permutations

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ₖ(n,t) f k ( n , t ) of permutations of \1, , n\ { 1 , ⋯ , n } that t -shatter all subsets of size k ? For t ≤ 2 t ≤ 2 , fₖ(n,t) = Θ (1) f k ( n , t ) = Θ ( 1 ) . Spencer showed that fₖ(n,t) = Θ (log log n) f k ( n , t ) = Θ ( log log n ) for 3 ≤ t ≤ k 3 ≤ t ≤ k and fₖ(n,k!) = Θ (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ₖ(n,t) = Θ (log n) f k ( n , t ) = Θ ( log n ) for $$t > 2 (k-1)!$$ <mml:mat