We introduce and study a simple Markovian model of random separable permutations. Our first main result is the almost sure convergence of these permutations towards a random limiting object in the sense of permutons, which we call the recursive separable permuton. We then prove several results on this new limiting object: a characterization of its distribution via a fixed-point equation, a combinatorial formula for its expected pattern densities, an explicit integral formula for its intensity measure, and lastly, we prove that its distribution is absolutely singular with respect to that of the Brownian separable permuton, which is the large size limit of uniform random separable permutations.
Révisé le :
Accepté le :
Publié le :
Keywords: permutons, permutation patterns, random combinatorial structures
Féray, Valentin 1 ; Rivera-Lopez, Kelvin 2
CC-BY-NC-ND 4.0
@article{CML_2023__15__45_0,
author = {F\'eray, Valentin and Rivera-Lopez, Kelvin},
title = {The permuton limit of random recursive separable permutations},
journal = {Confluentes Mathematici},
pages = {45--82},
year = {2023},
publisher = {Institut Camille Jordan},
volume = {15},
doi = {10.5802/cml.92},
language = {en},
url = {https://www.numdam.org/articles/10.5802/cml.92/}
}
TY - JOUR AU - Féray, Valentin AU - Rivera-Lopez, Kelvin TI - The permuton limit of random recursive separable permutations JO - Confluentes Mathematici PY - 2023 SP - 45 EP - 82 VL - 15 PB - Institut Camille Jordan UR - https://www.numdam.org/articles/10.5802/cml.92/ DO - 10.5802/cml.92 LA - en ID - CML_2023__15__45_0 ER -
%0 Journal Article %A Féray, Valentin %A Rivera-Lopez, Kelvin %T The permuton limit of random recursive separable permutations %J Confluentes Mathematici %D 2023 %P 45-82 %V 15 %I Institut Camille Jordan %U https://www.numdam.org/articles/10.5802/cml.92/ %R 10.5802/cml.92 %G en %F CML_2023__15__45_0
Féray, Valentin; Rivera-Lopez, Kelvin. The permuton limit of random recursive separable permutations. Confluentes Mathematici, Tome 15 (2023), pp. 45-82. doi: 10.5802/cml.92
[1] Two first-order logics of permutations, J. Comb. Theory, Ser. A, Volume 171 (2020) no. 46, 105158 | Zbl | MR
[2] The continuum random tree. III, Ann. Probab., Volume 21 (1993) no. 1, pp. 248-289 | Zbl | MR
[3] Triangulating the circle, at random, Am. Math. Mon., Volume 101 (1994) no. 3, pp. 223-233 | Zbl | DOI | MR
[4] Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, Combin. Theory, Volume 2 (2022) no. 3, 15, 35 pages | Zbl | MR
[5] The Brownian limit of separable permutations, Ann. Probab., Volume 46 (2018) no. 4, pp. 2134-2189 | Zbl | MR
[6] Universal limits of substitution-closed permutation classes, J. Eur. Math. Soc., Volume 22 (2020) no. 11, pp. 3565-3639 | Zbl | DOI | MR
[7] Random cographs: Brownian graphon limit and asymptotic degree distribution, Random Struct. Algorithms, Volume 60 (2022) no. 2, pp. 166-200 | Zbl | DOI | MR
[8] Degree sequence of random permutation graphs, Ann. Appl. Probab., Volume 27 (2017) no. 1, pp. 439-484 | Zbl | MR
[9] The Skew Brownian permuton: a new universality class for random constrained permutations, Proc. Lond. Math. Soc., Volume 126 (2023) no. 6, pp. 1842-1883 | Zbl | DOI | MR
[10] Permutons, meanders, and SLE-decorated Liouville quantum gravity (2022) | arXiv
[11] Baxter permuton and Liouville quantum gravity, Probab. Theory Relat. Fields, Volume 186 (2023) no. 3-4, pp. 1225-1273 | Zbl | DOI | MR
[12] Pattern matching for permutations, Inf. Process. Lett., Volume 65 (1998) no. 5, pp. 277-283 | Zbl | MR | DOI
[13] An elementary proof of the triangle inequality for the Wasserstein metric, Proc. Am. Math. Soc., Volume 136 (2008) no. 1, pp. 333-339 | Zbl | DOI | MR
[14] Random recursive triangulations of the disk via fragmentation theory, Ann. Probab., Volume 39 (2011) no. 6, pp. 2224-2270 | Zbl | MR
[15] Analytic combinatorics, Cambridge University Press, 2009 | Zbl | DOI
[16] Convex hulls of random order types, 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings (Leibniz Zentrum für Informatik), Volume 164, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 49 | DOI | MR | Zbl
[17] Ranks, copulas, and permutons, Metrika (2023)
[18] Limits of permutation sequences, J. Comb. Theory, Ser. B, Volume 103 (2013) no. 1, pp. 93-113 | Zbl | DOI | MR
[19] Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | Zbl | MR
[20] On the Brownian separable permuton, Comb. Probab. Comput., Volume 29 (2020) no. 2, pp. 241-266 | Zbl | DOI | MR
[21] The degree-restricted random process is far from uniform (2022) | arXiv
[22] The infinite limit of separable permutations, Random Struct. Algorithms, Volume 59 (2021) no. 4, pp. 622-639 | Zbl | DOI | MR
[23] Note on the heights of random recursive trees and random -ary search trees, Random Struct. Algorithms, Volume 5 (1994) no. 2, pp. 337-347 | Zbl | DOI | MR
[24] Graphon convergence of random cographs, Random Struct. Algorithms, Volume 59 (2021) no. 3, pp. 464-491 | Zbl | DOI | MR
[25] SageMath, the Sage Mathematics Software System (Version 9.4), 2021 (https://www.sagemath.org)
Cité par Sources :
