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ₖ (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) = (n) f k (n, t) = Θ (log log n) for 3 t k 3 ≤ t ≤ k and fₖ (n, k!) = (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) = (n) f k (n, t) = Θ (log n) for t > 2 (k-1) ! <mml: mat
Girão et al. (Wed,) studied this question.