Large Deviations for Permutations Avoiding Monotone Patterns

Abstract

For a given permutation $\tau$, let $P_N^{\tau }$ be the uniform probability distribution on the set of $N$-element permutations $\sigma$ that avoid the pattern $\tau$. For $\tau ={\mu }_k:=123\cdots k$, we consider $P_N^{{\mu }_k}({\sigma }_I=J)$ where $I\sim \gamma N$ and $J\sim \delta N$ for $\gamma ,\delta \in (0,1)$. If $\gamma +\delta \ne 1$ then we are in the large deviations regime with the probability decaying exponentially, and we calculate the limiting value of $P_N^{{\mu }_k}({\sigma }_I=J{)}^{1/N}$. We also observe that for $\tau ={\lambda }_{k,\ell }:=12\dots \ell k(k-1)\dots (\ell +1)$ and $\gamma +\delta <1$, the limit of $P_N^{\tau }({\sigma }_I=J{)}^{1/N}$ is the same as for $\tau ={\mu }_k$.

23 pages, 4 figures