Results on long twins in random words and permutations

Abstract

We study long $r$-twins in random words and permutations. Motivated by questions posed in works of Dudek-Grytczuk-Ruciński, we obtain the following. For a uniform word in $[k{]}^n$ we prove sharp one-sided tail bounds showing that the maximum $r$-power length (the longest contiguous block that can be partitioned into $r$ identical subblocks) is concentrated around $\frac{\log n}{(r-1)\log k}$. For random permutations, we prove that for fixed $k$ and $r\to \infty$, a uniform permutation of $[rk]$ a.a.s. contains $r$ disjoint increasing subsequences of length $k$, generalizing a previous result that proves this for $k=2$. Finally, we use a computer-aided pattern count to improve the best known lower bound on the length of alternating twins in a random permutation to $\hat{I}{\pm }_n\ge \left(\frac{1}{3}+0.0989-o(1)\right)n$, strengthening the previous constant.

12 pages, 1 figure