The Brownian limit of separable permutations. (English) Zbl 1430.60013

Summary: We study uniform random permutations in an important class of pattern-avoiding permutations: the separable permutations. We describe the asymptotics of the number of occurrences of any fixed given pattern in such a random permutation in terms of the Brownian excursion. In the recent terminology of permutons, our work can be interpreted as the convergence of uniform random separable permutations towards a “Brownian separable permuton”.


60C05 Combinatorial probability
05A05 Permutations, words, matrices


Full Text: DOI arXiv Euclid


[1] Albert, M., Homberger, C. and Pantone, J. (2015). Equipopularity classes in the separable permutations. Electron. J. Combin.22 Paper 2.2. · Zbl 1310.05006
[2] Albert, M. H. and Atkinson, M. D. (2005). Simple permutations and pattern restricted permutations. Discrete Math.300 1-15. DOI:10.1016/j.disc.2005.06.016. · Zbl 1073.05002
[3] Aldous, D. (1993). The continuum random tree. III. Ann. Probab.21 248-289. · Zbl 0791.60009
[4] Atapour, M. and Madras, N. (2014). Large deviations and ratio limit theorems for pattern-avoiding permutations. Combin. Probab. Comput.23 160-200. · Zbl 1304.60015
[5] Avis, D. and Newborn, M. (1981). On pop-stacks in series. Util. Math.19 129-140. · Zbl 0461.68060
[6] Bassino, F., Bouvel, M., Féray, V., Gerin, L., Maazoun, M. and Pierrot, A. Universal limits of substitution-closed permutation classes. Available at arXiv:1706.08333.
[7] Bevan, D. (2015). On the growth of permutation classes Ph.D. thesis, Open University. Available at arXiv:1506.06688. · Zbl 1311.05003
[8] Billingsley, P. (1999). Convergence of Probability Measures, 2nd ed. Wiley, New York. DOI:10.1002/9780470316962. · Zbl 0944.60003
[9] Bogachev, V. I. (2007). Measure Theory, Vol. 2. Springer, Berlin. · Zbl 1120.28001
[10] Bóna, M. (2010). The absence of a pattern and the occurrences of another. Discrete Math. Theor. Comput. Sci.12 89-102. · Zbl 1278.05007
[11] Bóna, M. (2012). Surprising symmetries in objects counted by Catalan numbers. Electron. J. Combin.19 Paper 62.
[12] Bóna, M. (2012). Combinatorics of Permutations, 2nd ed. Chapman-Hall and CRC Press, London.
[13] Bose, P., Buss, J. F. and Lubiw, A. (1998). Pattern matching for permutations. Inform. Process. Lett.65 277-283. DOI:10.1016/S0020-0190(97)00209-3. · Zbl 1338.68304
[14] Cheng, S.-E., Eu, S.-P. and Fu, T.-S. (2007). Area of Catalan paths on a checkerboard. European J. Combin.28 1331-1344. · Zbl 1115.05003
[15] The Sage Developers (2016). Sage mathematics software (Version 7.1). Availabel at http://www.sagemath.org.
[16] Dokos, T. and Pak, I. (2014). The expected shape of random doubly alternating Baxter permutations. Online J. Anal. Comb.9 Article 5. · Zbl 1292.05022
[17] Freedman, D. (2012). Brownian Motion and Diffusion, 3rd ed. Springer, Berlin. · Zbl 0231.60072
[18] Ghys, E. A Singular Mathematical Promenade. ENS Éditions, Lyon.
[19] Glebov, R., Grzesik, A., Klimosová, T. and Král’, D. (2015). Finitely forcible graphons and permutons. J. Combin. Theory Ser. B110 112-135. · Zbl 1302.05200
[20] Hoffman, C., Rizzolo, D. and Slivken, E. (2016). Pattern avoiding permutations and Brownian excursion part II: Fixed points. Probab. Theory Related Fields169 377-424. · Zbl 1407.60017
[21] Hoffman, C., Rizzolo, D. and Slivken, E. (2017). Pattern avoiding permutations and Brownian excursion part I: Shapes and fluctuations. Random Structures Algorithms50 394-419. · Zbl 1364.05003
[22] Homberger, C. (2012). Expected patterns in permutation classes. Electron. J. Combin.19 Paper 43. · Zbl 1253.05009
[23] Hoppen, C., Kohayakawa, Y., Moreira, C. G., Rath, B. and Sampaio, R. M. (2013). Limits of permutation sequences. J. Combin. Theory Ser. B103 93-113. · Zbl 1255.05174
[24] Janson, S. (2017). Patterns in random permutations avoiding the pattern \(132\). Combin. Probab. Comput.26 24-51. · Zbl 1381.60028
[25] Janson, S., Nakamura, B. and Zeilberger, D. (2015). On the asymptotic statistics of the number of occurrences of multiple permutation patterns. J. Comb.6 117-143. · Zbl 1312.05011
[26] Kallenberg, O. (2006). Foundations of Modern Probability, Springer, New York. · Zbl 0892.60001
[27] Kenyon, R., Král’, D., Radin, Ch. and Winkler, P. (2015). Permutations with fixed pattern densities (previous title: A variational principle for permutations). Available at arXiv:1506.02340.
[28] Kitaev, S. (2011). Patterns in Permutations and Words. Springer, Berlin. · Zbl 1257.68007
[29] Kortchemski, I. (2012). Invariance principles for Galton-Watson trees conditioned on the number of leaves. Stochastic Process. Appl.122 3126-3172. DOI:10.1016/j.spa.2012.05.013. · Zbl 1259.60103
[30] Le Gall, J.-F. (2005). Random trees and applications. Probab. Surv.2 245-311. · Zbl 1189.60161
[31] Madras, N. and Liu, H. (2010). Random pattern-avoiding permutations. In Algorithmic, Probability and Combinatorics. Contemp. Math.520 173-194. Amer. Math. Soc., Providence, RI. · Zbl 1209.05005
[32] Madras, N. and Pehlivan, L. (2016). Structure of random 312-avoiding permutations. Random Structures Algorithms49 599-631. DOI:10.1002/rsa.20601. · Zbl 1349.05006
[33] Miner, S. and Pak, I. (2014). The shape of random pattern-avoiding permutations. Adv. in Appl. Math.55 86-130. · Zbl 1300.05032
[34] Mörters, P. and Peres, Y. (2010). Brownian Motion. Cambridge Univ. Press, Cambridge.
[35] Pitman, J. (2006). Combinatorial Stochastic Processes, 2002 Saint-Flour Lecture Notes. Lecture Notes in Math.1875. Springer, Berlin.
[36] Pitman, J. and Rizzolo, D. (2015). Schröder’s problems and scaling limits of random trees. Trans. Amer. Math. Soc.367 6943-6969. DOI:10.1090/S0002-9947-2015-06254-0. · Zbl 1323.60024
[37] Rudolph, K. (2013). Pattern popularity in 132-avoiding permutations. Electron. J. Combin.20 Paper 8. · Zbl 1267.05013
[38] Shapiro, L. and Stephens, A. B. (1991). Bootstrap percolation, the Schröder numbers, and the \(n\)-kings problem. SIAM J. Discrete Math.4 275-280. · Zbl 0736.05008
[39] Vatter, V. (2015). Permutation classes. In Handbook of Enumerative Combinatorics 753-833. CRC Press, Boca Raton, FL. · Zbl 1353.05010
[40] Westenberg, M. A., Roerdink, J. B. T. M., Kuipers, O. P. and van Hijum, S. A. F. T. (2010). Random graphs and complex networks. Lecture notes. Available at http://www.win.tue.nl/ rhofstad/.
[41] Wikipedia. Enumerations of specific permutation classes. Available at https://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes. Accessed on Jan. 5th, 2016.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.