Small families of partially shattering permutations

2024/07/08 by Girão, António, Michel, Lukas, Tamitegama, Youri
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2407.05773

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_k(n,t) of permutations of \1, …, n\ that t-shatter all subsets of size k? For t ≤ 2, f_k(n,t) = Θ(1). Spencer showed that f_k(n,t) = Θ(log log n) for 3 ≤ t ≤ k and 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 affirmatively and proved that f_k(n,t) = Θ(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 ≥ 4. We establish that f_k(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_k(n,t) = Θ(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.

Related

• Shattering k-sets with Permutations
• Set Systems and Families of Permutations with Small Traces
• Shattering Thresholds for Random Systems of Sets, Words, and Permutations
• Maximum shattering
• Forbidding just one intersection, for permutations