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) of permutations of \1, , n\ that t-shatter all subsets of size k? For t ≤ 2, fₖ(n,t) = Θ(1). Spencer showed that fₖ(n,t) = Θ(log log n) for 3 ≤ t ≤ k and fₖ(n,k!) = Θ(log n). In 1996, F\"uredi asked whether partial shattering with permutations must always fall into one of these three regimes. Johnson and Wickes recently settled the case $k = 3$ affirmatively and proved that fₖ(n,t) = Θ(log n) for $t > 2 (k-1)!$. We give a surprising negative answer to the question of F\"uredi by showing that a fourth regime exists for k ≥ 4. We establish that fₖ(n,t) = Θ(√log n) for certain values of t and prove that this is the only other regime when $k = 4$. We also show that fₖ(n,t) = Θ(log n) for t > 2ᵏ⁻¹. This greatly narrows the range of t for which the asymptotic behaviour of fₖ(n,t) is unknown.