Number of linear orderings of a set to have balanced frequencies of triple orders 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).  It is tempting to conjecture that $6$ is always enough...but that'd be a bit surprising.
 A: 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.
A: With a colleague we are currently working on a similar problem: we want all 6 orderings to appear, though we do not care whether they happen with the same frequency. The lower bound transfers to your problem, however:
Let us assume that you have a "good" set of permutations $P_1,...,P_k$, and think of the positions of the value $1$ in all these permutations. For every value different from 1, store in a binary vector whether it appears before (noted 0) or after (noted 1) in the ordering. Because all 3-orders must appear, all n-1 vectors your built must be different. Thus, $k\geq \log_2(n-1)$. This technique is used, for instance, in this paper: http://arxiv.org/abs/1502.06888
To be sure that all 3-orders appear, we currently need $\leq 2.85\cdot \log_2(n)+O(1)$ permutations, and we are trying to close the gap. The construction wouldn't work for equal frequencies, however.
