Let $S$ be a set of $n$ elements and let $Q = (s\_1, s\_2, \ldots, s\_n)$ be a linear ordering of $S$. We write $s\_i <\_Q s\_j$ when $s\_i$ appears before $s\_j$ in $Q$.


I want to construct a set (or possibly a multi-set) of orderings $\mathcal{Q} = \{Q\_1, \ldots, Q\_k\}$ such that for every $a,b,c \in S$, each of the $6$ possible ordering of $a,b$ and $c$ occurs with the same frequency in $\mathcal{Q}$. Said differently, I want, for every $a,b,c \in S$, 


$$\Pr\_{Q \in \mathcal{Q}}[a <\_Q b <\_Q c] = 1/6$$


Now, the set of all $n!$ orderings satisfies this property.
Can we make $\mathcal{Q}$ smaller? What is the minimum number of orderings to get this property? In particular, can $|\mathcal{Q}|$ be polynomial in $n$?


For $n =3$ and $n = 4$, six orderings suffice (see [this stackexchange post](https://math.stackexchange.com/questions/1815973/number-of-linear-orderings-of-a-set-to-have-balanced-frequencies-of-triple-order)). It is tempting to conjecture that $6$ is always enough...but that'd be a bit surprising.



Number of linear orderings of a set to have balanced frequencies of triple orders
Let $c\_n$ be the minimum number of linear orders needed. So $c\_n$ is a multiple of $6$ and $c\_3=c\_4=6.$ 


As noted $c\_5 \gt 6.$ Here is another proof that it is impossible even if we relax the requirement to be that for each distinguished element $a$, among the $6\binom42=36$ ordered triples containing it (counted with multiplicity), there are $12$ each of the forms $axy,xay$ and $xya.$ Suppose we have $6$ linear orders. An element $a$ which appears in the center once must do so exactly three times since each such appearance gives one triple $axy$ , we need $12$ in all, and any other position gives $0,3$ or $6.$ However these three give $12$ orders of the form $xay$ so the other three must have $a$ at the beginning or end so contribute $6$ or $0$ orders of the form $axy.$ This does not allow for a total of $12.$


Also, $c\_m \le c\_n$ for $m \le n:$ Given a (multi)-set of $c\_n$ linear orders of $n$ elements of the desired type, delete all but $m$ elements to get a multiset for those elements.


If I had to guess, I'd guess that $O(\log n)$ is enough. However that is just a hunch. However $O(n^3)$ is enough even with a much stronger property:


If $q$ is a prime-power then the Special Linear group SL$(2,q)$ of order $q^3-q$ acts on the projective line with $n=q+1$ elements and is transitive on ordered triples. So any one orbit of its action on linear orders suffices and has the much stronger property that each ordered triple appears exactly once in any three given positions.


