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$.




---



Betweenness in permutations
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](http://www.jstor.org/stable/2031803) 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](http://www.sciencedirect.com/science/article/pii/S0195669885800287) or in [this paper by Kalmanson](http://www.sciencedirect.com/science/article/pii/0097316573900812).


