The skew Brownian permuton: a new universality class for random constrained permutations. (English) Zbl 1539.60006
This paper constructs the called skew Brownian permuton, which describes the limits of several models of random constrained permutations. The skew Brownian permuton is parameterized by two real parameters. For a specific choice of the parameters it coincides with the Baxter permuton. For another specific choice of the parameters, the skew Brownian permuton is proved to coincide with the biased Brownian separable permuton, a one-parameter family of permutons previously studied in the literature as the limit of uniform permutations in substitution-closed classes.
The skew Brownian permuton is constructed in terms of flows of solutions of certain stochastic differential equations driven by two-dimensional correlated Brownian excursions in the nonnegative quadrant. The existence and uniqueness of (strong) solutions for these new stochastic differential equations are proved. In addition, the author shows that some natural permutons arising from Liouville quantum gravity spheres decorated with two Schramm-Loewner evolution curves are skew Brownian permutons and such permutons cover almost the whole range of possible parameters. Some connections between constrained permutations and decorated planar maps have been investigated in the literature at the discrete level; this paper establishes this connection directly at the continuum level.
The skew Brownian permuton is constructed in terms of flows of solutions of certain stochastic differential equations driven by two-dimensional correlated Brownian excursions in the nonnegative quadrant. The existence and uniqueness of (strong) solutions for these new stochastic differential equations are proved. In addition, the author shows that some natural permutons arising from Liouville quantum gravity spheres decorated with two Schramm-Loewner evolution curves are skew Brownian permutons and such permutons cover almost the whole range of possible parameters. Some connections between constrained permutations and decorated planar maps have been investigated in the literature at the discrete level; this paper establishes this connection directly at the continuum level.
Reviewer: Ping Sun (Shenyang)
MSC:
| 60C05 | Combinatorial probability |
| 05A05 | Permutations, words, matrices |
| 34K50 | Stochastic functional-differential equations |
| 60J67 | Stochastic (Schramm-)Loewner evolution (SLE) |
| 81T40 | Two-dimensional field theories, conformal field theories, etc. in quantum mechanics |
References:
| [1] | N.Alon, C.Defant, and N.Kravitz, The runsort permuton, Adv. Appl. Math.139 (2022), Paper No. 102361, 18. · Zbl 1491.05003 |
| [2] | M.Albert, C.Homberger, and J.Pantone, Equipopularity classes in the separable permutations, Electron. J. Combin.22 (2015), no. 2, Paper 2.2, 18. · Zbl 1310.05006 |
| [3] | J.Aru, N.Holden, E.Powell, and X.Sun, Mating of trees for critical Liouville quantum gravity, arXiv:2109.00275, 2021. |
| [4] | D.Avis and M.Newborn, On pop‐stacks in series, Utilitas Math.19 (1981), 129-140. · Zbl 0461.68060 |
| [5] | G. E.Baxter, On fixed points of the composite of commuting functions, Proc. Amer. Math. Soc.15 (1964), 851-855. · Zbl 0126.38701 |
| [6] | F.Bassino, M.Bouvel, M.Drmota, V.Féray, L.Gerin, M.Maazoun, and A.Pierrot, Linear‐sized independent sets in random cographs and increasing subsequences in separable permutations, arXiv:2104.07444, 2021. |
| [7] | 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 |
| [8] | F.Bassino, M.Bouvel, V.Féray, L.Gerin, M.Maazoun, and A.Pierrot, Universal limits of substitution‐closed permutation classes, J. Eur. Math. Soc. (JEMS)22 (2020), no. 11, 3565-3639. · Zbl 1469.60039 |
| [9] | 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, Adv. Math.405 (2022), Paper No. 108513. · Zbl 1509.60013 |
| [10] | J.Bertoin, Markovian growth‐fragmentation processes, Bernoulli23 (2017), no. 2, 1082-1101. · Zbl 1375.60129 |
| [11] | N.Bonichon, M.Bousquet‐Mélou, and É.Fusy, Baxter permutations and plane bipolar orientations, Sém. Lothar. Combin.61A (2009/11), Art. B61Ah, 29. · Zbl 1205.05004 |
| [12] | M.Bóna, Exact enumeration of 1342‐avoiding permutations: a close link with labeled trees and planar maps, J. Combin. Theory Ser. A80 (1997), no. 2, 257-272. · Zbl 0887.05004 |
| [13] | J.Borga, Random permutations —a geometric point of view, Ph.D. thesis. arXiv:2107.09699, 2021. |
| [14] | J.Borga, The permuton limit of strong‐Baxter and semi‐Baxter permutations is the skew Brownian permuton, Electron. J. Probab.27 (2022), 1-53. · Zbl 1515.60038 |
| [15] | J.Borga, M.Bouvel, V.Féray, and B.Stufler, A decorated tree approach to random permutations in substitution‐closed classes, Electron. J. Probab.25 (2020), Paper No. 67, 52. · Zbl 1456.60030 |
| [16] | J.Borga, E.Duchi, and E.Slivken, Almost square permutations are typically square, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques57 (2021), no. 4, 1834-1856. · Zbl 1483.05002 |
| [17] | J.Borga, E.Gwynne, and X.Sun, Permutons, meanders, and SLE‐decorated Liouville quantum gravity, arXiv:2207.02319, 2022. |
| [18] | J.Borga, N.Holden, X.Sun, and P.Yu, Baxter permuton and Liouville quantum gravity, arXiv:2203.12176, 2022. (To appear in Probability Theory and Related Fields.) |
| [19] | J.Borga and M.Maazoun, Scaling and local limits of Baxter permutations and bipolar orientations through coalescent‐walk processes, Ann. Probab.50 (2022), no. 4, 1359-1417. · Zbl 1504.60163 |
| [20] | J.Borga and E.Slivken, Square permutations are typically rectangular, Ann. Appl. Probab.30 (2020), no. 5, 2196-2233. · Zbl 1475.60017 |
| [21] | P.Bose, J. F.Buss, and A.Lubiw, Pattern matching for permutations, Inform. Process. Lett.65 (1998), no. 5, 277-283. · Zbl 1338.68304 |
| [22] | M.Bousquet‐Mélou, É.Fusy, and K.Raschel, Plane bipolar orientations and quadrant walks, Sém. Lothar. Combin.81 (2020), Art. B81l, 64. |
| [23] | M.Bouvel, V.Guerrini, A.Rechnitzer, and S.Rinaldi, Semi‐Baxter and strong‐Baxter: two relatives of the Baxter sequence, SIAM J. Discrete Math.32 (2018), no. 4, 2795-2819. · Zbl 1401.05022 |
| [24] | W. M.Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms2 (1967), 19-26; addendum, ibid. 3 (1967), 25-26. · Zbl 0266.05009 |
| [25] | K.Burdzy and H.Kaspi, Lenses in skew Brownian flow, Ann. Probab.32 (2004), no. 4, 3085-3115. · Zbl 1071.60073 |
| [26] | M.Çağlar, H.Hajri, and A. H.Karakuş, Correlated coalescing Brownian flows on \(\mathbb{R}\) and the circle, ALEA Lat. Am. J. Probab. Math. Stat.15 (2018), no. 2, 1447-1464. · Zbl 1403.60045 |
| [27] | F.‐R. K.Chung, R. L.Graham, V. E.Hoggatt, Jr, and M.Kleiman, The number of Baxter permutations, J. Combin. Theory Ser. A24 (1978), no. 3, 382-394. · Zbl 0398.05003 |
| [28] | D.Dauvergne, The archimedean limit of random sorting networks, J. Amer. Math. Soc. (2021). |
| [29] | D.Denisov and V.Wachtel, Random walks in cones, Ann. Probab.43 (2015), no. 3, 992-1044. · Zbl 1332.60066 |
| [30] | S.Dulucq, S.Gire, and J.West, Permutations with forbidden subsequences and nonseparable planar maps, Discrete Math.153 (1996), no. 1‐3, 85-103. · Zbl 0853.05047 |
| [31] | B.Duplantier, J.Miller, and S.Sheffield, Liouville quantum gravity as a mating of trees, Astérisque (2021), no. 427, viii+257. · Zbl 1503.60003 |
| [32] | J.Duraj and V.Wachtel, Invariance principles for random walks in cones, Stochastic Process. Appl.130 (2020), no. 7, 3920-3942. · Zbl 1456.60103 |
| [33] | S.Felsner, É.Fusy, M.Noy, and D.Orden, Bijections for Baxter families and related objects, J. Combin. Theory Ser. A118 (2011), no. 3, 993-1020. · Zbl 1238.05010 |
| [34] | E. R.Fernholz, T.Ichiba, I.Karatzas, and V.Prokaj, Planar diffusions with rank‐based characteristics and perturbed Tanaka equations, Probab. Theory Related Fields156 (2013), no. 1-2, 343-374. · Zbl 1274.60247 |
| [35] | E.Fusy, E.Narmanli, and G.Schaeffer, On the enumeration of plane bipolar posets and transversal structures, Extended abstracts EuroComb 2021, Springer, Berlin, 2021, pp. 560-566. |
| [36] | R.Glebov, A.Grzesik, T.Klimošová, and D.Král’, Finitely forcible graphons and permutons, J. Combin. Theory Ser. B110 (2015), 112-135. · Zbl 1302.05200 |
| [37] | E.Gwynne, N.Holden, and X.Sun, Joint scaling limit of a bipolar‐oriented triangulation and its dual in the peanosphere sense, arXiv:1603.01194, 2016. |
| [38] | E.Gwynne, N.Holden, and X.Sun, Mating of trees for random planar maps and Liouville quantum gravity: a survey, arXiv:1910.04713, 2019. |
| [39] | H.Hajri, Stochastic flows related to Walsh Brownian motion, Electron. J. Probab.16 (2011), no. 58, 1563-1599. · Zbl 1245.60067 |
| [40] | H.Hajri, Discrete approximations to solution flows of Tanaka’s SDE related to Walsh Brownian motion, Séminaire de Probabilités XLIV, Lecture Notes in Math., vol. 2046, Springer, Heidelberg, 2012, pp. 167-190. · Zbl 1261.60054 |
| [41] | H.Hajri, On flows associated to Tanaka’s SDE and related works, Electron. Commun. Probab.20 (2015), no. 16, 12. · Zbl 1327.60118 |
| [42] | J. M.Harrison and L. A.Shepp, On skew Brownian motion, Ann. Probab.9 (1981), no. 2, 309-313. · Zbl 0462.60076 |
| [43] | C.Hoppen, Y.Kohayakawa, C. G.Moreira, B.Ráth, and R. M.Sampaio, Limits of permutation sequences, J. Combin. Theory Ser. B103 (2013), no. 1, 93-113. · Zbl 1255.05174 |
| [44] | I.Karatzas and S. E.Shreve, Brownian motion and stochastic calculus, 2nd ed., Graduate Texts in Mathematics, vol. 113, Springer, New York, 1991. · Zbl 0734.60060 |
| [45] | S.Kitaev, P.Salimov, C.Severs, and H.Ulfarsson, Restricted non‐separable planar maps and some pattern avoiding permutations, Discrete Appl. Math.161 (2013), no. 16-17, 2514-2526. · Zbl 1285.05003 |
| [46] | A.Lejay, On the constructions of the skew Brownian motion, Probab. Surv.3 (2006), 413-466. · Zbl 1189.60145 |
| [47] | J.‐F.Le Gall, Applications du temps local aux équations différentielles stochastiques unidimensionnelles, Seminar on probability, XVII, Lecture Notes in Math., vol. 986, Springer, Berlin, 1983, pp. 15-31. · Zbl 0527.60062 |
| [48] | J.‐F.Le Gall, One‐dimensional stochastic differential equations involving the local times of the unknown process, Stochastic analysis and applications (Swansea, 1983), Lecture Notes in Math., vol. 1095, Springer, Berlin, 1984, pp. 51-82. · Zbl 0551.60059 |
| [49] | Y.Le Jan and O.Raimond, Flows, coalescence and noise, Ann. Probab.32 (2004), no. 2, 1247-1315. · Zbl 1065.60066 |
| [50] | Y.Le Jan and O.Raimond, Flows associated to Tanaka’s SDE, ALEA Lat. Am. J. Probab. Math. Stat.1 (2006), 21-34. · Zbl 1105.60038 |
| [51] | Y.Le Jan and O.Raimond, Flows, coalescence and noise. A correction, Ann. Probab.48 (2020), no. 3, 1592-1595. · Zbl 1443.60063 |
| [52] | Y.Li, X.Sun, and S. S.Watson, Schnyder woods, SLE (16), and Liouville quantum gravity, arXiv:1705.03573, 2017. |
| [53] | L.Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. · Zbl 1292.05001 |
| [54] | M.Maazoun, On the Brownian separable permuton, Combin. Probab. Comput.29 (2020), no. 2, 241-266. · Zbl 1478.60027 |
| [55] | C. L.Mallows, Baxter permutations rise again, J. Combin. Theory Ser. A27 (1979), no. 3, 394-396. · Zbl 0427.05005 |
| [56] | J.Miller and S.Sheffield, Imaginary geometry IV: interior rays, whole‐plane reversibility, and space‐filling trees, Probab. Theory Related Fields169 (2017), no. 3‐4, 729-869. · Zbl 1378.60108 |
| [57] | J.Miller and S.Sheffield, Liouville quantum gravity spheres as matings of finite‐diameter trees, Ann. Inst. Henri Poincaré Probab. Stat.55 (2019), no. 3, 1712-1750. · Zbl 1448.60168 |
| [58] | S.Nakao, On the pathwise uniqueness of solutions of one‐dimensional stochastic differential equations, Osaka Math. J.9 (1972), 513-518. · Zbl 0255.60039 |
| [59] | C. B.Presutti and W.Stromquist, Packing rates of measures and a conjecture for the packing density of 2413, Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge University Press, Cambridge, 2010, pp. 287-316. · Zbl 1217.05053 |
| [60] | V.Prokaj, The solution of the perturbed Tanaka‐equation is pathwise unique, Ann. Probab.41 (2013), no. 3B, 2376-2400. · Zbl 1284.60134 |
| [61] | D.Romik, Permutations with short monotone subsequences, Adv. Appl. Math.37 (2006), no. 4, 501-510. · Zbl 1109.05015 |
| [62] | L.Shapiro and A. B.Stephens, Bootstrap percolation, the Schröder numbers, and the \(N\)‐kings problem, SIAM J. Discrete Math.4 (1991), no. 2, 275-280. · Zbl 0736.05008 |
| [63] | S.Starr, Thermodynamic limit for the Mallows model on \(S_n\), J. Math. Phys.50 (2009), no. 9, 095208, 15. · Zbl 1241.82039 |
| [64] | S.Starr and M.Walters, Phase uniqueness for the Mallows measure on permutations, J. Math. Phys.59 (2018), no. 6, 063301, 28. · Zbl 1459.82099 |
| [65] | S.Watanabe, The stochastic flow and the noise associated to Tanaka’s stochastic differential equation, Ukraïn. Mat. Zh.52 (2000), no. 9, 1176-1193. · Zbl 0971.60062 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
