Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-06T18:48:52.520Z Has data issue: false hasContentIssue false
  • English
  • Français

Large Deviations and Ratio Limit Theorems for Pattern-Avoiding Permutations

Published online by Cambridge University Press:  13 December 2013

MAHSHID ATAPOUR  and
NEAL MADRAS
MAHSHID ATAPOUR
Affiliation:
Department of Finance and Management Science, University of Saskatchewan, 25 Campus Drive, Saskatoon, Saskatchewan S7N 5A7, Canada (e-mail: atapour@math.usask.ca)
NEAL MADRAS
Affiliation:
Department of Mathematics and Statistics, York University, 4700 Keele Street, Toronto, Ontario M3J 1P3, Canada (e-mail: madras@mathstat.yorku.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

Primary 60C05Secondary 05A0505A1660F10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 2 , March 2014 , pp. 161 - 200
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Albert, M. H., Elder, M., Rechnitzer, A., Westcott, P. and Zabrocki, M. (2006) On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. Appl. Math. 36 96–105.CrossRefGoogle Scholar
[2]Alon, N. and Friedgut, E. (2000) On the number of permutations avoiding a given pattern. J. Combin. Theory Ser. A 89 133–140.CrossRefGoogle Scholar
[3]Arratia, R. (1999) On the Stanley–Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin. 6 N1.Google Scholar
[4]Atkinson, M. D. and Stitt, T. (2002) Restricted permutations and the wreath product. Discrete Math. 259 19–36.CrossRefGoogle Scholar
[5]Backelin, J., West, J. and Xin, G. (2001) Wilf equivalence for singleton classes. In Proc. 13th Conference on Formal Power Series and Algebraic Combinatorics, Tempe, AZ, 2001.Google Scholar
[6]Bóna, M. (1999) The solution of a conjecture of Stanley and Wilf for all layered patterns. J. Combin. Theory Ser. A 85 96–104.CrossRefGoogle Scholar
[7]Bóna, M. (2004) Combinatorics of Permutations, Chapman & Hall/CRC.Google Scholar
[8]Bóna, M. (2007) New records in Stanley–Wilf limits. Europ. J. Combin. 28 75–85.Google Scholar
[9]Bóna, M. A new upper bound for 1324-avoiding permutations. Preprint. arXiv:1207.2379Google Scholar
[10]Bousquet-Mélou, M., Claesson, A., Dukes, M. and Kitaev, S. (2010) (2+2)-free posets, ascent sequences and pattern avoiding permutations. J. Combin. Theory Ser. A 117 884–909.CrossRefGoogle Scholar
[11]Claesson, A., Jelínek, V. and Steingrímsson, E. (2012) Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. J. Combin. Theory Ser. A 119 1680–1691.Google Scholar
[12]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[13]Hammersley, J. M. and Whittington, S. G. (1985) Self-avoiding walks in wedges. J. Phys. A: Math. Gen. 18 101–111.Google Scholar
[14]Kesten, H. (1963) On the number of self-avoiding walks. J. Math. Phys. 4 960–969.Google Scholar
[15]Madras, N. and Liu, H. (2010) Random pattern-avoiding permutations. In Algorithmic Probability and Combinatorics (Lladser, M. E.et al., eds), Vol. 520 of Contemporary Mathematics, AMS.Google Scholar
[16]Madras, N. and Pehlivan, L. Structure of random 312-avoiding permutations. In preparation.Google Scholar
[17]Madras, N. and Slade, G. (1993) The Self-Avoiding Walk, Birkhäuser.Google Scholar
[18]Marcus, A. and Tardos, G. (2004) Excluded permutation matrices and the Stanley–Wilf conjecture. J. Combin. Theory Ser. A 107 153–160.Google Scholar
[19]Miner, S. and Pak, I. The shape of random pattern avoiding permutations. Preprint. arXiv:1303.7313Google Scholar
[20]Regev, A. (1981) Asymptotic values for degrees associated with strips of Young diagrams. Adv. Math. 41 115–136.Google Scholar
[21]Simon, R. and Schmidt, F. W. (1985) Restricted permutations. Europ. J. Combin. 6 383–406.Google Scholar