×

zbMATH — the first resource for mathematics

A decorated tree approach to random permutations in substitution-closed classes. (English) Zbl 07225521
This paper analyzes random permutations from substitution-closed classes via a probabilistic approach. Given a substitution-closed class \(C\) with the set \(S\) of simple permutations for \(i\) in \([n]\), the generating function of \(S\) is also denoted by \(S\) for convenience. Its radius of convergence is denoted by \(\rho_S\). For a permutation \(v\) and a pattern \(\pi\), denote by \(c\)-\(occ(\pi,v)\) the number of consecutive occurrences of pattern \(\pi\) in \(v\). Suppose that \(S'(\rho_S)\ge1/(1+\rho_S)^2-1\). Consider a uniform random permutation \(v_n\) of size \(n\) in \(C\), where \(n\) is any positive integer. By identifying the packed forest associated with a uniform random permutation in a substitution-closed class as a conditioned mono-type Galton-Waston forest, it is shown that for each pattern \(\pi\in C\), there exists \(\gamma\in[0,1]\) such that \(\frac1n c\)-\(occ(\pi,v_n)\rightarrow\gamma\) in probability as \(n\) tends to infinity.

MSC:
60C05 Combinatorial probability
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
05A05 Permutations, words, matrices
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] R. Abraham, J.-F. Delmas, and H. Guo, Critical multi-type Galton-Watson trees conditioned to be large, J. Theoret. Probab. 31 (2018), no. 2, 757-788. · Zbl 1422.60146
[2] M. Albert and M. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), no. 1, 1-15. · Zbl 1073.05002
[3] D. Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab. 1 (1991), no. 2, 228-266. · Zbl 0733.60016
[4] D. Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), no. 1, 1-28. · Zbl 0722.60013
[5] D. Aldous, The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990), London Math. Soc. Lecture Note Ser., vol. 167, Cambridge Univ. Press, Cambridge, 1991, pp. 23-70. · Zbl 0931.41017
[6] D. Aldous, The continuum random tree. III, Ann. Probab. 21 (1993), no. 1, 248-289. · Zbl 0791.60009
[7] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot, Universal limits of substitution-closed permutation classes, Preprint arXiv:1706.08333, to appear in J. Eur. Math. Soc., 2017.
[8] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot, Scaling limits of permutation classes with a finite specification: a dichotomy, Preprint arXiv:1903.07522, 2019.
[9] F. Bassino, M. Bouvel, V. Féray, L. Gerin, and A. Pierrot, The Brownian limit of separable permutations, Ann. Probab. 46 (2018), no. 4, 2134-2189. · Zbl 1430.60013
[10] I. Benjamini and O. Schramm, Recurrence of distributional limits of finite planar graphs, Electronic Journal of Probability 6 (2001). · Zbl 1010.82021
[11] G. H. Berzunza Ojeda, On scaling limits of multitype Galton-Watson trees with possibly infinite variance, ALEA Lat. Am. J. Probab. Math. Stat. 15 (2018), no. 1, 21-48. · Zbl 1378.60110
[12] D. I. Bevan, On the growth of permutation classes, Ph.D. thesis, The Open University, https://arxiv.org/abs/1506.06688, 2015. · Zbl 1311.05003
[13] J. Borga, Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\), Probab. Theory Related Fields 176 (2020), no. 1-2, 449-531. · Zbl 1434.60035
[14] J. Borga, E. Duchi, and E. Slivken, Almost square permutations are typically square, (2019), Preprint arXiv:1910.04813.
[15] J. Borga and E. Slivken, Square permutations are typically rectangular, Preprint arXiv:1904.03080, to appear in Annals of Applied Probability, 2019.
[16] M. Bouvel, C. Chauve, M. Mishna, and D. Rossin, Average-case analysis of perfect sorting by reversals, Discrete Mathematics, Algorithms and Applications 3 (2011), no. 3, 369-392. · Zbl 1408.05005
[17] J. Chover, P. Ney, and S. Wainger, Functions of probability measures, J. Analyse Math. 26 (1973), 255-302. · Zbl 0276.60018
[18] L. de Raphélis, Scaling limit of multitype Galton-Watson trees with infinitely many types, Ann. Inst. H. Poincaré Probab. Statist. 53 (2017), no. 1, 200-225. · Zbl 1369.60059
[19] L. Devroye and S. Janson, Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees, Random Structures Algorithms 38 (2011), no. 4, 381-395. · Zbl 1223.05049
[20] T. Dokos and I. Pak, The expected shape of random doubly alternating Baxter permutations, Online J. Anal. Comb. 9 (2014), 12. · Zbl 1292.05022
[21] R. Ehrenborg and M. Méndez, Schröder parenthesizations and chordates, Journal of Combinatorial Theory, Series A 67 (1994), no. 2, 127-139. · Zbl 0804.05021
[22] S. Foss, D. Korshunov, and S. Zachary, An introduction to heavy-tailed and subexponential distributions, second ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2013. · Zbl 1274.62005
[23] B. V. Gnedenko and A. N. Kolmogorov, Limit distributions for sums of independent random variables, Addison-Wesley Publishing Company, Inc., Cambridge, Mass., 1954, Translated and annotated by K. L. Chung. With an Appendix by J. L. Doob. · Zbl 0056.36001
[24] C. Hoffman, D. Rizzolo, and E. Slivken, Pattern-avoiding permutations and Brownian excursion Part I: shapes and fluctuations, Random Structures Algorithms 50 (2017), no. 3, 394-419. · Zbl 1364.05003
[25] C. Hoffman, D. Rizzolo, and E. Slivken, Pattern-avoiding permutations and Brownian excursion, part II: fixed points, Probab. Theory Related Fields 169 (2017), no. 1-2, 377-424. · Zbl 1407.60017
[26] C. Hoffman, D. Rizzolo, and E. Slivken, Fixed points of 321-avoiding permutations, Proc. Amer. Math. Soc. 147 (2019), no. 2, 861-872. · Zbl 1439.60016
[27] C. Hoffman, D. Rizzolo, and E. Slivken, Scaling limits of permutations avoiding long decreasing sequences, Preprint arXiv:1911.04982, 2019. · Zbl 1439.60016
[28] C. Holmgren and S. Janson, Fringe trees, crump-mode-jagers branching processes and \(m\)-ary search trees, Probab. Surveys 14 (2017), 53-154. · Zbl 1406.60120
[29] C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, and R. Menezes Sampaio, Limits of permutation sequences, J. Combin. Theory Ser. B 103 (2013), no. 1, 93-113. · Zbl 1255.05174
[30] S. Janson, Random cutting and records in deterministic and random trees, Random Structures Algorithms 29 (2006), no. 2, 139-179. · Zbl 1120.05083
[31] S. Janson, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probability Surveys 9 (2012), 103-252. · Zbl 1244.60013
[32] S. Janson, Patterns in random permutations avoiding the pattern 321, Random Structures & Algorithms 55 (2019), no. 2, 249-270. · Zbl 1423.60026
[33] S. Janson, Patterns in random permutations avoiding some sets of multiple patterns, Algorithmica 82 (2020), no. 3, 616-641. · Zbl 1446.60010
[34] T. Jonsson and S. Stefánsson, Condensation in nongeneric trees, J. Stat. Phys. 142 (2011), no. 2, 277-313. · Zbl 1225.60140
[35] O. Kallenberg, Random measures, theory and applications, Springer, 2017. · Zbl 1376.60003
[36] G. Kersting, On the height profile of a conditioned Galton-Watson tree, arXiv preprint arXiv:1101.3656 (2011).
[37] I. Kortchemski, Invariance principles for Galton-Watson trees conditioned on the number of leaves, Stochastic Process. Appl. 122 (2012), no. 9, 3126-3172. · Zbl 1259.60103
[38] I. Kortchemski, Limit theorems for conditioned non-generic Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat. 51 (2015), no. 2, 489-511. · Zbl 1315.60091
[39] G. Labelle, Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. in Math. 42 (1981), no. 3, 217-247. · Zbl 0477.05007
[40] M. Maazoun, On the brownian separable permuton, Combinatorics, Probability and Computing 29 (2020), no. 2, 241-266.
[41] A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), no. 1, 153-160. · Zbl 1051.05004
[42] G. Miermont, Invariance principles for spatial multitype Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008), no. 6, 1128-1161. · Zbl 1178.60058
[43] S. Miner and I. Pak, The shape of random pattern-avoiding permutations, Adv. in Appl. Math. 55 (2014), 86-130. · Zbl 1300.05032
[44] R. G. Pinsky, The infinite limit of random permutations avoiding patterns of length three, Combinatorics, Probability and Computing 29 (2020), no. 1, 137-152. · Zbl 1434.60052
[45] J. Pitman and D. Rizzolo, Schröder’s problems and scaling limits of random trees, Trans. Amer. Math. Soc. 367 (2015), no. 10, 6943-6969. · Zbl 1323.60024
[46] D. Rizzolo, Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set, Ann. Inst. Henri Poincaré Probab. Stat. 51 (2015), no. 2, 512-532. · Zbl 1319.60170
[47] R. Stephenson, Local convergence of large critical multi-type Galton-Watson trees and applications to random maps, J. Theoret. Probab. 31 (2018), no. 1, 159-205. · Zbl 1393.05244
[48] B. Stufler, Limits of random tree-like discrete structures, Preprint arXiv:1612.02580, 2016.
[49] B. Stufler, Gibbs partitions: The convergent case, Random Structures & Algorithms 53 (2018), no. 3, 537-558. · Zbl 1398.05184
[50] B. Stufler, Random enriched trees with applications to random graphs, Electronic Journal of Combinatorics 25 (2018), no. 3. · Zbl 1393.60013
[51] B. Stufler, Local limits of large Galton-Watson trees rerooted at a random vertex, Ann. Inst. H. Poincaré Probab. Statist. 55 (2019), no. 1, 155-183. · Zbl 07039768
[52] B.
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.