Skip to main content
deleted 2 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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 $n^2-n$$O(n^3)$ is enough even with a much stronger property:

If $q$ is a prime-power then the Projective Special Special Linear group PSLSL$(2,q)$ of order $\frac{q^3-q}2$ (or twice that if $q$ is even)$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 added conditionmuch stronger property that each ordered triple appears equally oftenexactly once in any three given positions.

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 $n^2-n$ is enough:

If $q$ is a prime-power then the Projective Special Linear group PSL$(2,q)$ of order $\frac{q^3-q}2$ (or twice that if $q$ is even) 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 added condition that each ordered triple appears equally often in any three positions.

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.

Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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 $n^2-n$ is enough:

If $q$ is a prime-power then the Projective Special Linear group PSL$(2,q)$ of order $\frac{q^3-q}2$ (or twice that if $q$ is even) 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 added condition that each ordered triple appears equally often in any three positions.