6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 6 does not fit even for $n=5$. Indeed, each element should occur between two others exactly 20 times. Each order gives 0,3,4,3,0 such pairs to its elements. So, from six 4s, twelve 3s and twelve 0s you need to combine five 20s, which is impossible. $\endgroup$
    – Ilya Bogdanov
    Commented Jun 8, 2016 at 14:42
  • $\begingroup$ I like the argument, but I'm missing how you get $20$ for $n = 5$? For a fixed element, there are $4$ ways to choose a predecessor, and then $3$ ways for a successor, which yields $12$ ways of being sandwiched. Does that make sense? $\endgroup$
    – Manuel Lafond
    Commented Jun 8, 2016 at 17:15
  • 1
    $\begingroup$ Oh yes,,sorry, 20 would be for $n=6$. But then $12$ should be composed thrice as $4\times 3+2\times 0$ and twice as $3\times 4+2\times 0$. An element $a$ of the first type appear once at the first position, once at the last, twice at second and twice at the fourth one. When $a$ is on the first place, it has 6 pairs to the right. These pairs should appear for the second time (when $a$ is at the second position). But $K_4$ does not split into two $K_3$... $\endgroup$
    – Ilya Bogdanov
    Commented Jun 8, 2016 at 18:10
  • 1
    $\begingroup$ A very weak bound showing that the size of $Q$ must tend to infinity with $n$: WLOG (for ease of notation) assume the first permutation is $123…n$. Now let $a_1=3$ and $a_k=a_{k-1}^2+1$. It follows from repeated applications of Erdős–Szekeres that in any collection of $k$ permutations of $1,2,…,a_k$ there must be some subset of size $3$ that is simultaneously monotonic in every permutation, and by pigeonhole that there is a subset of size $3$ sorted the same way in $k/2$ different permutations. So if $n=a_k$ you need at least $6(k/2)=Ω(\log \log n)$ permutations. $\endgroup$
    – Kevin P. Costello
    Commented Jun 9, 2016 at 0:51

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Marvelous! Exactly what I was looking for, thank you. $\endgroup$
    – Manuel Lafond
    Commented Jun 9, 2016 at 21:22
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Any two vectors should differ in at most two coordinates, which gives $k\geq 2\log_2(n-1)$... $\endgroup$
    – Ilya Bogdanov
    Commented Oct 17, 2016 at 21:07
  • $\begingroup$ no, that gives $\log_2(n-1)+1$ at best: consider all vectors of length $n$, and append to each of them a bit equal to its XOR. Any two vectors are now at distance $\geq 2$, yet you only increased their length by 1. We were able to improve the lower bound to $1.38\log_2(n)$ asymptotically, however. Still not there yet :-/ $\endgroup$
    – Nathann Cohen
    Commented Oct 17, 2016 at 21:30
  • $\begingroup$ Oh, yes, sorry --- I mixed up $+1$ inside and outside $\log$... $\endgroup$
    – Ilya Bogdanov
    Commented Oct 17, 2016 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .