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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.