×

zbMATH — the first resource for mathematics

Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\). (English) Zbl 1434.60035
Summary: We set up a new notion of local convergence for permutations and we prove a characterization in terms of proportions of consecutive pattern occurrences. We also characterize random limiting objects for this new topology introducing a notion of “shift-invariant” property (corresponding to the notion of unimodularity for random graphs). We then study two models in the framework of random pattern-avoiding permutations. We compute the local limits of uniform \(\rho \)-avoiding permutations, for \(|\rho |=3,\) when the size of the permutations tends to infinity. The core part of the argument is the description of the asymptotics of the number of consecutive occurrences of any given pattern. For this result we use bijections between \(\rho \)-avoiding permutations and rooted ordered trees, local limit results for Galton-Watson trees, the Second moment method and singularity analysis.

MSC:
60C05 Combinatorial probability
05A05 Permutations, words, matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abraham, R., Delmas, J.-F.: An introduction to Galton-Watson trees and their local limits. ArXiv preprint:arXiv:1506.05571 (2015)
[2] Aldous, D., Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab., 1, 2, 228-266 (1991) · Zbl 0733.60016
[3] Aldous, D., The continuum random tree I, Ann. Probab., 19, 1, 1-28 (1991) · Zbl 0722.60013
[4] Aldous, D., The continuum random tree II: an overview, Stoch. Anal., 167, 23-70 (1991) · Zbl 0791.60008
[5] Aldous, D., The continuum random tree III, Ann. Probab., 21, 1, 248-289 (1993) · Zbl 0791.60009
[6] Aldous, D., Tree-valued Markov chains derived from Galton-Watson processes, Annales de l’Institut Henri Poincare (B) Probability and Statistics, 34, 5, 637-686 (1998) · Zbl 0917.60082
[7] Aldous, David; Steele, J. Michael, The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence, Probability on Discrete Structures, 1-72 (2004), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1037.60008
[8] Angel, O.; Schramm, O., Uniform infinite planar triangulations, Commun. Math. Phys., 241, 2-3, 191-213 (2003) · Zbl 1098.60010
[9] Bassino, F., Bouvel, M., Féray, V., Gerin, L., Maazoun, M., Pierrot, A.: Universal limits of substitution-closed permutation classes. J. Eur. Math. Soc. ArXiv preprint:arXiv:1706.08333 (2017)
[10] Bassino, F.; Bouvel, M.; Féray, V.; Gerin, L.; Pierrot, A., The Brownian limit of separable permutations, Ann. Probab., 46, 4, 2134-2189 (2018) · Zbl 1430.60013
[11] Benjamini, I.; Schramm, O., Recurrence of distributional limits of finite planar graphs, Electron. J. Probab., 6, 23, 13 (2001) · Zbl 1010.82021
[12] Bertoin, J.; Pitman, J., Path transformations connecting Brownian bridge, excursion and meander, Bull. des Sci. Math., 118, 2, 147-166 (1994) · Zbl 0805.60076
[13] Billingsley, P., Probability and Measure (2008), London: Wiley, London
[14] Billingsley, P., Convergence of Probability Measures (2013), London: Wiley, London · Zbl 0172.21201
[15] Bóna, M., The absence of a pattern and the occurrences of another, Discrete Math. Theor. Comput. Sci., 12, 2, 89-102 (2010) · Zbl 1278.05007
[16] Bóna, M., Surprising symmetries in objects counted by Catalan numbers, Electron. J. Comb., 19, 1, 62 (2012) · Zbl 1243.05006
[17] Bóna, M., Combinatorics of Permutations (2016), London: Chapman and Hall/CRC, London
[18] Borga, J., Bouvel, M., V. Féray, Stufler, B.: A decorated tree approach to random permutations in substitution-closed classes. ArXiv preprint: arXiv:1904.07135 (2019)
[19] Borga, J., Slivken, E.: Square permutations are typically rectangular. ArXiv preprint: arXiv:1904.03080 (2019)
[20] Claesson, A.; Kitaev, S., Classification of bijections between 321-and 132-avoiding permutations, Sém. Lothar. de Combin., 60, B60d (2008) · Zbl 1179.05006
[21] Crane, H.; Desalvo, S.; Elizalde, S., The probability of avoiding consecutive patterns in the Mallows distribution, Random Struct. Algorithms, 53, 3, 417-447 (2018) · Zbl 1401.05010
[22] Devroye, L.; Janson, S., Protected nodes and fringe subtrees in some random trees, Electron. Commun. Probab., 19, 6, 10 (2014) · Zbl 1355.60015
[23] Elizalde, Sergi, A survey of consecutive patterns in permutations, Recent Trends in Combinatorics, 601-618 (2016), Cham: Springer International Publishing, Cham · Zbl 1354.05004
[24] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge: Cambridge University Press, Cambridge
[25] Frenkel, P., Convergence of graphs with intermediate density, Trans. Am. Math. Soc., 370, 5, 3363-3404 (2018) · Zbl 1380.05061
[26] Hoffman, C.; Rizzolo, D.; Slivken, E., Pattern-avoiding permutations and Brownian excursion part I: shapes and fluctuations, Random Struct. Algorithms, 50, 3, 394-419 (2017) · Zbl 1364.05003
[27] Hoffman, C.; Rizzolo, D.; Slivken, E., Pattern-avoiding permutations and Brownian excursion, part II: fixed points, Probab. Theory Relat. Fields, 169, 1-2, 377-424 (2017) · Zbl 1407.60017
[28] Hoffman, C.; Rizzolo, D.; Slivken, E., Fixed points of 321-avoiding permutations, Proc. Am. Math. Soc., 147, 2, 861-872 (2019) · Zbl 1439.60016
[29] Holmgren, C.; Janson, S., Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees, Probab. Surv., 14, 53-154 (2017) · Zbl 1406.60120
[30] Hoppen, C.; Kohayakawa, Y.; Moreira, Cg; Ráth, B.; Sampaio, Rm, Limits of permutation sequences, J. Comb. Theory Ser. B, 103, 1, 93-113 (2013) · Zbl 1255.05174
[31] Janson, S., The Wiener index of simply generated random trees, Random Struct. Algorithms, 22, 4, 337-358 (2003) · Zbl 1025.05021
[32] Janson, S., Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., 9, 103-252 (2012) · Zbl 1244.60013
[33] Janson, S., Patterns in random permutations avoiding the pattern 132, Comb. Probab. Comput., 26, 1, 24-51 (2017) · Zbl 1381.60028
[34] Janson, S.: Patterns in random permutations avoiding some sets of multiple patterns. ArXiv preprint: arXiv:1804.06071 (2018)
[35] Janson, S.: Patterns in random permutations avoiding the pattern 321. Random Struct. Algorithms (2018) · Zbl 1423.60026
[36] Kallenberg, O., Random Measures, Theory and Applications (2017), Berlin: Springer, Berlin
[37] Kenyon, R., Dominos and the Gaussian free field, Ann. Probab., 29, 3, 1128-1137 (2001) · Zbl 1034.82021
[38] Kenyon, R., Kral, D., Radin, C., Winkler, P.: Permutations with fixed pattern densities. ArXiv preprint: arXiv:1506.02340 (2015)
[39] Kesten, H., Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincaré Probab. Stat., 22, 4, 425-487 (1986) · Zbl 0632.60106
[40] Krikun, M.: Local structure of random quadrangulations. ArXiv preprint: arXiv:math/0512304 (2005)
[41] Le Gall, J-F, Uniqueness and universality of the Brownian map, Ann. Probab., 41, 4, 2880-2960 (2013) · Zbl 1282.60014
[42] Lovász, L., Large Networks and Graph Limits (2012), Providence: American Mathematical Society, Providence · Zbl 1292.05001
[43] Maazoun, M.: On the Brownian separable permuton. ArXiv preprint: arXiv:1711.08986 (2017)
[44] Madras, N.; Pehlivan, L., Structure of random 312-avoiding permutations, Random Struct. Algorithms, 49, 3, 599-631 (2016) · Zbl 1349.05006
[45] Marckert, J-F; Mokkadem, A., Limit of normalized quadrangulations: the Brownian map, Ann. Probab., 34, 6, 2144-2202 (2006) · Zbl 1117.60038
[46] Miermont, G., The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math., 210, 2, 319-401 (2013) · Zbl 1278.60124
[47] Miner, S.; Pak, I., The shape of random pattern-avoiding permutations, Adv. Appl. Math., 55, 86-130 (2014) · Zbl 1300.05032
[48] Neveu, J., Arbres et processus de Galton-Watson, Ann. de l’Inst. Henri Poincaré. Probab. et Stat., 22, 2, 199-207 (1986) · Zbl 0601.60082
[49] Otter, R., The multiplicative process, Ann. Math. Stat., 20, 206-224 (1949) · Zbl 0033.38301
[50] Pinsky, R.: The infinite limit of random permutations avoiding patterns of length three. ArXiv preprint: arXiv:1806.07669 (2018)
[51] Rahman, M., Virag, B., Vizer, M.: Geometry of permutation limits. ArXiv preprint: arXiv:1609.03891 (2016) · Zbl 1449.60010
[52] Sheffield, S., Gaussian free fields for mathematicians, Probab. Theory Relat. Fields, 139, 3-4, 521-541 (2007) · Zbl 1132.60072
[53] Starr, S., Thermodynamic limit for the Mallows model on \({S}_n\), J. Math. Phys., 50, 9, 095208 (2009) · Zbl 1241.82039
[54] Stephenson, R., Local convergence of large critical multi-type Galton-Watson trees and applications to random maps, J. Theor. Probab., 31, 1, 159-205 (2018) · Zbl 1393.05244
[55] Stufler, Benedikt, Local limits of large Galton-Watson trees rerooted at a random vertex, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 55, 1, 155-183 (2019) · Zbl 07039768
[56] Vatter, V.: Permutation classes. In: Handbook of Enumerative Combinatorics, Discrete Math. Appl. (Boca Raton), pp. 753-833. CRC Press, Boca Raton (2015) · Zbl 1353.05010
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.