Results on long twins in random words and permutations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912630306766848 |
|---|---|
| author | Liu, Elliott Tang, Linus Wan, Jessica |
| author_facet | Liu, Elliott Tang, Linus Wan, Jessica |
| contents | 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 $α_n \ge \left(\tfrac{1}{3}+0.0989-o(1)\right)n$, strengthening the previous constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Results on long twins in random words and permutations Liu, Elliott Tang, Linus Wan, Jessica Combinatorics Probability 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 $α_n \ge \left(\tfrac{1}{3}+0.0989-o(1)\right)n$, strengthening the previous constant. |
| title | Results on long twins in random words and permutations |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2510.04335 |