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) = \Theta (1)\) . Spencer showed that \(f_k(n,t) = \Theta (\log \log n)\) for \(3 \le t \le k\) and \(f_k(n,k!) = \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) = \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) = \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) = \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.
