On the growth rate of the Stanley-Wilf limit of blockable permutations

Abstract

Given a permutation $\pi$, let ${\text{Av}}_n(\pi )$ be the number of permutations of length $n$ that avoid $\pi$ as a subpermutation. The celebrated resolution of the Stanley-Wilf conjecture by Marcus and Tardos confirmed that the limit $L(\pi )={\lim }_{n\to \infty }|{\text{Av}}_n(\pi ){|}^{1/n}$ exists. A central and challenging question concerns the behavior of $L(\pi )$ as a function of the pattern length $|\pi |$. While Fox proved that $L(\pi )$ is exponential in $|\pi |$ for almost all permutations, it is known that $L(\pi )$ grows polynomially for specific structural classes. For instance, $L(\pi )$ is known to be quadratic in $|\pi |$ when $\pi$ is a monotone or a layered permutation. In this paper, we address this question for {\it blockable} permutations $\pi$.