Order-isomorphic twins in permutations

Let $a_1,\dotsc,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 $Ω(n^{3/5})$ improving the trivial bound of $Ω(n^{1/2})$. We also show that a random permutation contains twins of length $Ω(n^{2/3})$, which is sharp.

No reviews yet.

No comments yet.