# Betweenness in permutations

Let us consider permutations $\pi$ on $\{1,\dots,n\}$ as sequences $\pi(1),\pi(2),\dots,\pi(n)$. For a permutation $\pi$ let $R(\pi)$ be the ternary relation with $(x,y,z)\in R(\pi)$ whenever element $y$ appears in between $x$ and $z$ (i.e., x is left of y and z is right of y, or, x is right of y and z is left of y). So $(x,y,z)\in R(\pi)$ iff $(z,y,x)\in R$.

My question is: For permutations of length $n$, what is the smallest number $f(n)\ge 1$ such that there exist permutations $\pi_1,\dots,\pi_{f(n)}$ with $R(\pi_1)\cap R(\pi_2)\cap \dots \cap R(\pi_{f(n)})=\emptyset$? Are there exact results or bounds known describing this sequence?

Examples: For n=2, $f(n)=1$ since $R(\pi)=\emptyset$ for all permutations $\pi$ of length 2. For n>2, $f(n)$ has to be larger than 1 because $R(\pi)$ is only empty if $n\le2$.

For n=3, we can take the permutations $\pi_1=123$ and $\pi_2=132$. Here $R(\pi_1)=\{(1,2,3),(3,2,1)\}$ and $R(\pi_2)=\{(1,3,2),(2,3,1)\}$. Thus $R(\pi_1)\cap R(\pi_2)=\emptyset$ and $f(3)=2$.

For n=4, the permutations $\pi_1=1234$ and $\pi_2=2143$ show that $f(4)=2$.

For n=5, $f(n)\ge 3$. This is not hard to see but requires a few case distinctions.

With support of computer calculation we managed to establish that $f(n)=3$ for $n\in\{5,\dots,16\}$ and $f(n)>3$ for $n>16$.

Without loss of generality, we may assume that $\pi_1=12\dots n$.

By the Erdős–Szekeres lemma, $\pi_2$ has a monotone subsequence of length at least $\sqrt{n}$. In other words, there is a subset $S_2 \subseteq \{1,2,\dots,n\}$ of size at least $\sqrt{n}$ where $R(\pi_1)$ and $R(\pi_2)$ coincide. By induction, for any $k$ permutations, there is a subset $S_k \subseteq \{1,2,\dots,n\}$ of size at least $n^{1/2^{k-1}}$ that is monotone in each of the $k$ permutations, and so the relations $R(\pi_1), \dots, R(\pi_k)$ coincide on $S_k$. If $|S_k|\ge 3$, then $R(\pi_1) \cap \dots \cap R(\pi_k) \neq \emptyset$. To get $n^{1/2^{k-1}}\le 2$, we need $2^{2^{k-1}}\ge n$. This gives the lower bound $f(n)\ge 1+\log\log{n}$, where the logarithms are base $2$.

This paper by Kruskal claims that a general form of this result was proved by De Bruijn and that, in fact, the lower bound on $k$ (or, the upper bound on $n$ given $k$) is tight. A construction of $k$ permutations of length $2^{2^{k-1}}$ with no common monotone subsequence of length $3$ does not seem to be easy to describe. But for $k=3$ we can take $$\pi_2 = 13, 14, 15, 16, 9, 10, 11, 12, 5, 6, 7, 8, 1, 2, 3, 4 \\ \pi_3 = 11, 12, 9, 10, 15, 16, 13, 14, 3, 4, 1, 2, 7, 8, 5, 6.$$

A construction for arbitrary $k$ is described, for example, in this paper by Alon, Füredi and Katchalski or in this paper by Kalmanson.

• These are exactly the results and references I was hoping for! Thanks a lot! – Martin Lackner Jul 22 '16 at 9:27