Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2107.06974 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929278365466624 |
|---|---|
| author | Dudek, Andrzej Grytczuk, Jaroslaw Rucinski, Andrzej |
| author_facet | Dudek, Andrzej Grytczuk, Jaroslaw Rucinski, Andrzej |
| contents | 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)=Ω\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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_06974 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Multiple twins in permutations Dudek, Andrzej Grytczuk, Jaroslaw Rucinski, Andrzej Combinatorics 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)=Ω\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$. |
| title | Multiple twins in permutations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2107.06974 |