Scaling limits of permutation classes with a finite specification: a dichotomy
| العنوان: | Scaling limits of permutation classes with a finite specification: a dichotomy |
|---|---|
| المؤلفون: | Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, Adeline Pierrot |
| المساهمون: | Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Institut für Mathematik [Zürich], Universität Zürich [Zürich] = University of Zurich (UZH), Centre National de la Recherche Scientifique (CNRS), Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Unité de Mathématiques Pures et Appliquées (UMPA-ENSL), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon), Bioinformatique (LRI) (BioInfo - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Swiss National Science Foundation grant number 200021-17253, ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), ANR-16-CE40-0016,PPPP,Percolation et percolation de premier passage(2016), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Centre National de la Recherche Scientifique (CNRS) |
| المصدر: | Advances in Mathematics Advances in Mathematics, 2022, 405, pp.108513. ⟨10.1016/j.aim.2022.108513⟩ |
| بيانات النشر: | arXiv, 2019. |
| سنة النشر: | 2019 |
| مصطلحات موضوعية: | Combinatorial probability, automatic specification, General Mathematics, Probability (math.PR), Permutations, 60C05, 05A05, scaling limits, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], permutons, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], analytic combinatorics, FOS: Mathematics, Mathematics - Combinatorics, universality, Combinatorics (math.CO), permutation pattern, MSC 60C05, 05A05, Mathematics - Probability, Brownian CRT |
| الوصف: | We consider uniform random permutations in classes having a finite combinatorial specification for the substitution decomposition. These classes include (but are not limited to) all permutation classes with a finite number of simple permutations. Our goal is to study their limiting behavior in the sense of permutons. The limit depends on the structure of the specification restricted to families with the largest growth rate. When it is strongly connected, two cases occur. If the associated system of equations is linear, the limiting permuton is a deterministic $X$-shape. Otherwise, the limiting permuton is the Brownian separable permuton, a random object that already appeared as the limit of most substitution-closed permutation classes, among which the separable permutations. Moreover these results can be combined to study some non strongly connected cases. To prove our result, we use a characterization of the convergence of random permutons by the convergence of random subpermutations. Key steps are the combinatorial study, via substitution trees, of families of permutations with marked elements inducing a given pattern, and the singularity analysis of the corresponding generating functions. Comment: 72 pages, 27 figures; v4, improved presentation, for journal submission |
| تدمد: | 0001-8708 1090-2082 |
| DOI: | 10.48550/arxiv.1903.07522 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b9129320c5f267dc1d4500c9c6ca5015 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....b9129320c5f267dc1d4500c9c6ca5015 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 00018708 10902082 |
|---|---|
| DOI: | 10.48550/arxiv.1903.07522 |