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=\binom{ 2r-1}r$. 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$.
Categories: math.CO