logo Institut Camille Jordan

CONFLUENTES MATHEMATICI

logo UMPA
The permuton limit of random recursive separable permutations
Valentin Féray1 ; Kelvin Rivera-Lopez2
1 Université de Lorraine, CNRS, IECL, F-54000, Nancy, France
2 Department of Mathematics, Gonzaga University, Washington State, USA.
Confluentes Mathematici, Tome 15 (2023), pp. 45-82.

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/cml.92
Classification : 60C05, 05A05
Mots clés : permutons, permutation patterns, random combinatorial structures
Valentin Féray 1 ; Kelvin Rivera-Lopez 2

1 Université de Lorraine, CNRS, IECL, F-54000, Nancy, France
2 Department of Mathematics, Gonzaga University, Washington State, USA.
Licence : CC-BY-NC-ND 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{CML_2023__15__45_0,
     author = {Valentin F\'eray and Kelvin Rivera-Lopez},
     title = {The permuton limit of random recursive separable permutations},
     journal = {Confluentes Mathematici},
     pages = {45--82},
     publisher = {Institut Camille Jordan},
     volume = {15},
     year = {2023},
     doi = {10.5802/cml.92},
     language = {en},
     url = {https://cml.centre-mersenne.org/articles/10.5802/cml.92/}
}
TY  - JOUR
AU  - Valentin Féray
AU  - Kelvin Rivera-Lopez
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://cml.centre-mersenne.org/articles/10.5802/cml.92/
DO  - 10.5802/cml.92
LA  - en
ID  - CML_2023__15__45_0
ER  - 
%0 Journal Article
%A Valentin Féray
%A Kelvin Rivera-Lopez
%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://cml.centre-mersenne.org/articles/10.5802/cml.92/
%R 10.5802/cml.92
%G en
%F CML_2023__15__45_0
Valentin Féray; Kelvin Rivera-Lopez. The permuton limit of random recursive separable permutations. Confluentes Mathematici, Tome 15 (2023), pp. 45-82. doi : 10.5802/cml.92. https://cml.centre-mersenne.org/articles/10.5802/cml.92/

[1] Michael Albert; Mathilde Bouvel; Valentin Féray Two first-order logics of permutations, J. Comb. Theory, Ser. A, Volume 171 (2020) no. 46, 105158 | MR | Zbl

[2] David Aldous The continuum random tree. III, Ann. Probab., Volume 21 (1993) no. 1, pp. 248-289 | MR | Zbl

[3] David Aldous Triangulating the circle, at random, Am. Math. Mon., Volume 101 (1994) no. 3, pp. 223-233 | DOI | MR | Zbl

[4] Frédérique Bassino; Mathilde Bouvel; Michael Drmota; Valentin Féray; Lucas Gerin; Mickaël Maazoun; Adeline Pierrot Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, Combin. Theory, Volume 2 (2022) no. 3, 15, 35 pages | MR | Zbl

[5] Frédérique Bassino; Mathilde Bouvel; Valentin Féray; Lucas Gerin; Mickaël Maazoun; Adeline Pierrot The Brownian limit of separable permutations, Ann. Probab., Volume 46 (2018) no. 4, pp. 2134-2189 | MR | Zbl

[6] Frédérique Bassino; Mathilde Bouvel; Valentin Féray; Lucas Gerin; Mickaël Maazoun; Adeline Pierrot Universal limits of substitution-closed permutation classes, J. Eur. Math. Soc., Volume 22 (2020) no. 11, pp. 3565-3639 | DOI | MR | Zbl

[7] Frédérique Bassino; Mathilde Bouvel; Valentin Féray; Lucas Gerin; Mickaël Maazoun; Adeline Pierrot Random cographs: Brownian graphon limit and asymptotic degree distribution, Random Struct. Algorithms, Volume 60 (2022) no. 2, pp. 166-200 | DOI | MR | Zbl

[8] Bhaswar B. Bhattacharya; Sumit Mukherjee Degree sequence of random permutation graphs, Ann. Appl. Probab., Volume 27 (2017) no. 1, pp. 439-484 | MR | Zbl

[9] Jacopo Borga The Skew Brownian permuton: a new universality class for random constrained permutations, Proc. Lond. Math. Soc., Volume 126 (2023) no. 6, pp. 1842-1883 | DOI | MR | Zbl

[10] Jacopo Borga; Ewain Gwynne; Xin Sun Permutons, meanders, and SLE-decorated Liouville quantum gravity (2022) | arXiv

[11] Jacopo Borga; Nina Holden; Xin Sun; Pu Yu Baxter permuton and Liouville quantum gravity, Probab. Theory Relat. Fields, Volume 186 (2023) no. 3-4, pp. 1225-1273 | DOI | MR | Zbl

[12] Prosenjit Bose; Jonathan F. Buss; Anna Lubiw Pattern matching for permutations, Inf. Process. Lett., Volume 65 (1998) no. 5, pp. 277-283 | DOI | MR | Zbl

[13] Philippe Clement; Wolfgang Desch An elementary proof of the triangle inequality for the Wasserstein metric, Proc. Am. Math. Soc., Volume 136 (2008) no. 1, pp. 333-339 | DOI | MR | Zbl

[14] Nicolas Curien; Jean-François Le Gall Random recursive triangulations of the disk via fragmentation theory, Ann. Probab., Volume 39 (2011) no. 6, pp. 2224-2270 | MR | Zbl

[15] Philippe Flajolet; Robert Sedgewick Analytic combinatorics, Cambridge University Press, 2009 | DOI | Zbl

[16] Xavier Goaoc; Emo Welzl 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] Rudolf Grübel Ranks, copulas, and permutons, Metrika (2023)

[18] Carlos Hoppen; Yoshiharu Kohayakawa; Carlos G. Moreira; Balázs Ráth; Rudith M. Sampaio Limits of permutation sequences, J. Comb. Theory, Ser. B, Volume 103 (2013) no. 1, pp. 93-113 | DOI | MR | Zbl

[19] Svante Janson Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | MR | Zbl

[20] Mickaël Maazoun On the Brownian separable permuton, Comb. Probab. Comput., Volume 29 (2020) no. 2, pp. 241-266 | DOI | MR | Zbl

[21] Michael Molloy; Erlang Surya; Lutz Warnke The degree-restricted random process is far from uniform (2022) | arXiv

[22] R. Pinsky The infinite limit of separable permutations, Random Struct. Algorithms, Volume 59 (2021) no. 4, pp. 622-639 | DOI | MR | Zbl

[23] Boris Pittel Note on the heights of random recursive trees and random m-ary search trees, Random Struct. Algorithms, Volume 5 (1994) no. 2, pp. 337-347 | DOI | MR | Zbl

[24] Benedikt Stufler Graphon convergence of random cographs, Random Struct. Algorithms, Volume 59 (2021) no. 3, pp. 464-491 | DOI | MR | Zbl

[25] The Sage Developers SageMath, the Sage Mathematics Software System (Version 9.4), 2021 (https://www.sagemath.org)

Cité par Sources :