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_k(n,t)$ of permutations of $\{1,\dots ,n\}$ that $t$-shatter all subsets of size $k$? For $t\le 2$, $f_k(n,t)=\mathrm{\Theta }(1)$. Spencer showed that $f_k(n,t)=\mathrm{\Theta }(\log \log n)$ for $3\le t\le k$ and $f_k(n,k!)=\mathrm{\Theta }(\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$ affirmatively and proved that $f_k(n,t)=\mathrm{\Theta }(\log n)$ for $t>2(k-1)!$. We give a surprising negative answer to the question of Füredi by showing that a fourth regime exists for $k\ge 4$. We establish that $f_k(n,t)=\mathrm{\Theta }(\sqrt{\log n})$ for certain values of $t$ and prove that this is the only other regime when $k=4$. We also show that $f_k(n,t)=\mathrm{\Theta }(\log n)$ for $t>2^{k-1}$. This greatly narrows the range of $t$ for which the asymptotic behaviour of $f_k(n,t)$ is unknown.