Large Deviations and Ratio Limit Theorems for Pattern-Avoiding Permutations

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.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.