Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.22580 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909976849547264 |
|---|---|
| author | Sethi, Saksham Wei, Fan |
| author_facet | Sethi, Saksham Wei, Fan |
| contents | Given a permutation $π$, let $\text{Av}_n(π)$ be the number of permutations of length $n$ that avoid $π$ as a subpermutation. The celebrated resolution of the Stanley-Wilf conjecture by Marcus and Tardos confirmed that the limit $L(π) = \lim_{n \to \infty} |\text{Av}_n(π)|^{1/n}$ exists. A central and challenging question concerns the behavior of $L(π)$ as a function of the pattern length $|π|$. While Fox proved that $L(π)$ is exponential in $|π|$ for almost all permutations, it is known that $L(π)$ grows polynomially for specific structural classes. For instance, $L(π)$ is known to be quadratic in $|π|$ when $π$ is a monotone or a layered permutation. In this paper, we address this question for {\it blockable} permutations $π$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_22580 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the growth rate of the Stanley-Wilf limit of blockable permutations Sethi, Saksham Wei, Fan Combinatorics Given a permutation $π$, let $\text{Av}_n(π)$ be the number of permutations of length $n$ that avoid $π$ as a subpermutation. The celebrated resolution of the Stanley-Wilf conjecture by Marcus and Tardos confirmed that the limit $L(π) = \lim_{n \to \infty} |\text{Av}_n(π)|^{1/n}$ exists. A central and challenging question concerns the behavior of $L(π)$ as a function of the pattern length $|π|$. While Fox proved that $L(π)$ is exponential in $|π|$ for almost all permutations, it is known that $L(π)$ grows polynomially for specific structural classes. For instance, $L(π)$ is known to be quadratic in $|π|$ when $π$ is a monotone or a layered permutation. In this paper, we address this question for {\it blockable} permutations $π$. |
| title | On the growth rate of the Stanley-Wilf limit of blockable permutations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.22580 |