Article contents
Large Deviations and Ratio Limit Theorems for Pattern-Avoiding Permutations
Published online by Cambridge University Press: 13 December 2013
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.
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2013
References
- 12
- Cited by