Large Deviations and Ratio Limit Theorems for Pattern-Avoiding Permutations

Source abstract

For a fixed permutation τ, let $\mathcal{S}_N(\tau)$ be the set of permutations on N elements that avoid the pattern τ. Madras and Liu (2010) conjectured that $\lim_{N\rightarrow\infty}\frac{|\mathcal{S}_{N+1}(\tau)|}{ |\mathcal{S}_N(\tau)|}$ exists; if it does, it must equal the Stanley–Wilf limit. We prove the conjecture for every permutation τ of length 5 or less, as well as for some longer cases (including 704 of the 720 permutations of length 6). We also consider permutations drawn at random from $\mathcal{S}_N(\tau)$ , and we investigate properties of their graphs (viewing permutations as functions on {1,. . ., N }) scaled down to the unit square [0,1] 2 . We prove exact large deviation results for these graphs when τ has length 3; it follows, for example, that it is exponentially unlikely for a random 312-avoiding permutation to have points above the diagonal strip | y−x | < ε, but not unlikely to have points below the strip. For general τ, we show that some neighbourhood of the upper left corner of [0,1] 2 is exponentially unlikely to contain a point of the graph if and only if τ starts with its largest element. For patterns such as τ=4231 we establish that this neighbourhood can be extended along the sides of [0,1] 2 to come arbitrarily close to the corner points (0,0) and (1,1), as simulations had suggested.