2
$\begingroup$

Let $S$ be a set of $n$ elements and let $Q = (s_1, s_2, \ldots, s_n)$ be an 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 properties. Can we make $\mathcal{Q}$ smaller? What is the minimum number of orderings to get this property? Can $|\mathcal{Q}|$ be polynomial in $n$? With $n = 4$, I think $12 < 4!$ is enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.