Large deviations for permutations avoiding monotone patterns


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\ldots 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\neq 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}$.

In The Electronic Journal of Combinatorics, Volume 23, Issue 4, 2016, 1-20