Multiple twins in permutations

Abstract

By an $r$-tuplet in a permutation we mean a family of $r$ pairwise disjoint subsequences with the same relative order. The length of an $r$-tuplet is defined as the length of any single subsequence in the family. Let $t^{(r)}(n)$ denote the largest $k$ such that every permutation of length $n$ contains an $r$-tuplet of length $k$. We prove that $t^{(r)}(n)=O\left(n^{\frac{r}{2r-1}}\right)$ and $t^{(r)}(n)=\Omega \left(n^{\frac{R}{2R-1}}\right)$, where $R=\left(\genfrac{}{}{0ex}{}{2r-1}{r}\right)$. We conjecture that the upper bound brings the correct order of magnitude of $t^{(r)}(n)$ and support this conjecture by proving that it holds for almost all permutations. Our work generalizes previous studies of the case $r=2$.

Updated grant number