Small Families of Partially Shattering Permutations

Journal article

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 fk(n, t) of permutations of {1, ⋯, n} that t-shatter all subsets of size k? For t≤2, fk(n, t)=Θ(1). Spencer showed that fk(n, t)=Θ(loglogn) for 3≤t≤k and fk(n, k!)=Θ(logn). 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 fk(n, t)=Θ(logn) 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≥4. We establish that fk(n, t)=Θ(logn) for certain values of t and prove that this is the only other regime when k=4. We also show that fk(n, t)=Θ(logn) for t>2k-1. This greatly narrows the range of t for which the asymptotic behaviour of fk(n, t) is unknown.

Authors: Girão, A; Michel, L; Tamitegama, Y

• Alternative title: Small Families of Partially Shattering Permutations
• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Combinatorica
• Volume: 46
• Issue: 2
• Article number: 10
• Publication date: 2026-03-04
• Acceptance date: 2026-01-16
• DOI: 10.1007/s00493-026-00201-6
• EISSN: 1439-6912
• ISSN: 0209-9683
• Language: English