Abstract
Let n ∈ N and (π₁,π₂,...,π₆) be six permutations of the same ground set [n].
We say that the triple {a₁,a₂,a₃} ⊆ [n] is shattered by (π₁,π₂,...,π₆) if we can find all possible orderings in the set {(πᵢ(a₁),πᵢ(a₂),πᵢ(a₃)) : i ∈ [6]}.
A natural extremal question is, for a fixed n, what is the maximal number of triples that can be shattered in this way.
Using the flag algebra method, we prove that no six-tuple of permutations shatters more than 1/2 C(n,3)+O(n²) triples.
On the other hand, for every n, we construct six permutations of [n] that shatter at least 107/220 C(n,3) triples and we find exact values for 5 ≤ n ≤ 9.
These results improve the previously known bounds of Johnson and Wickes