Shattering triples with six permutations

Let \(n \in \mathbb{N}\) and \((\pi_1,\pi_2,\dots,\pi_6)\) be six permutations of the same ground set \([n]\). We say that the triple \(\{a_1,a_2,a_3\} \subset [n]\) is shattered by \((\pi_1,\pi_2,\dots,\pi_6)\) if we can find all possible orderings in the set \(\{(\pi_i(a_1),\pi_i(a_2),\pi_i(a_3)) : i \in [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 \(\frac12\binom{n}3+O(n^2)\) triples. On the other hand, for every \(n\), we construct six permutations of \([n]\) that shatter at least \(\frac{107}{220}\binom{n}3\) triples and we find exact values for \(5 \leq n \leq 9\). These results improve the previously known bounds of Johnson and Wickes.

This is a joint work with Alexander Clifton, Bartłomiej Kielak, and Jan Volec.