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}$. We also observe that for $\tau = \lambda_{k,\ell} := 12\ldots\ell k(k-1)\ldots(\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$.
@article{10_37236_6225,
author = {Neal Madras and Lerna Pehlivan},
title = {Large deviations for permutations avoiding monotone patterns},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {4},
doi = {10.37236/6225},
zbl = {1353.05009},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6225/}
}
TY - JOUR
AU - Neal Madras
AU - Lerna Pehlivan
TI - Large deviations for permutations avoiding monotone patterns
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/6225/
DO - 10.37236/6225
ID - 10_37236_6225
ER -
%0 Journal Article
%A Neal Madras
%A Lerna Pehlivan
%T Large deviations for permutations avoiding monotone patterns
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6225/
%R 10.37236/6225
%F 10_37236_6225
Neal Madras; Lerna Pehlivan. Large deviations for permutations avoiding monotone patterns. The electronic journal of combinatorics, Tome 23 (2016) no. 4. doi: 10.37236/6225
