Order-isomorphic twins in permutations

Abstract

Let $a_1,\dots ,a_n$ be a permutation of $[n]$. Two disjoint order-isomorphic subsequences are called \emph{twins}. We show that every permutation of $[n]$ contains twins of length $\Omega (n^{3/5})$ improving the trivial bound of $\Omega (n^{1/2})$. We also show that a random permutation contains twins of length $\Omega (n^{2/3})$, which is sharp.

3 pages