Project

Back to overview

Enumeration and limit shapes for pattern-avoiding permutations and related combinatorial objects

 Applicant Bouvel Mathilde 186872 Eccellenza Institut für Mathematik Universität Zürich University of Zurich - ZH Mathematics 01.01.2020 - 31.08.2021 395'331.00
Show all

Keywords (11)

permuton; graphon; graphs; trees; hereditary graph classes; permutations; combinatorics; pattern-avoiding permutations; limits of discrete structures; enumeration; discrete probability theory

Lay Summary (French)

Le projet proposé étudie les permutations et les graphes évitant certaines sous-structures (motifs ou sous-graphes induits). Partant de deux méthodes classiques (arbres de génération, et décompositions par substitution), nous proposons des directions innovantes pour l'étude de ces objets. Les résultats attendus sont : 1. des généralisations de la méthode des arbres de génération pour permettre la résolution de questions énumératives plus complexes ;2. un développement très original de cette méthode afin d'obtenir des résultats de forme limite (notamment locale) ; 3. la description de la forme limite de familles de graphes héréditaires, dans la topologie des graphons, en utilisant les décompositions de graphes.
Lay summary
Ce projet de recherche se situe en mathématiques discrètes, plus précisément à l'interface entre combinatoire et probabilités. Les objets étudiés sont principalement les permutations (les manières d'ordonner les entiers de 1 à n, pour tout n) et les graphes (décrits par un ensemble fini de sommets et un ensemble d'arêtes reliant certaines paires de sommets entre eux). Notre étude se concentre sur des familles de permutations et de graphes évitant certaines sous-structures (motifs ou sous-graphes induits). De telles restrictions sont désormais classiques et leur étude a fait l'objet de nombreux travaux.

Deux méthodes sont essentielles à notre projet: les arbres de génération, et les décompositions d'objets combinatoires (plus particulièrement, la "substitution decomposition" des permutations et les "modular" et "split decompositions" des graphes). La première est classique pour énumérer des familles de permutations évitant des motifs. La seconde est habituellement utilisée dans le cadre algorithmique. La décennie passée a vu émerger de nombreux travaux utilisant la "substitution decomposition" des permutations pour obtenir des résultats d'énumération. Et certains de nos travaux récents ont utilisé cette approche pour obtenir des résultats innovants sur la forme limite de permutations évitant des motifs.

Les objectifs de notre travail sont divers. Nous proposons d'abord deux généralisations de la méthode des arbres de génération, afin d'élargir son champ d'application pour l'obtention de résultats énumératifs. Un second développement, très original, vise à obtenir des résultats de forme limite (notamment locale) via cette méthode. Enfin, nous proposons d'utiliser les décompositions de graphes afin d'obtenir des résultats de forme limite dans la topologie des graphons.
 Direct link to Lay Summary Last update: 02.12.2019

Responsible applicant and co-applicants

Name Institute
 Bouvel Mathilde Institut für Mathematik Universität Zürich

Employees

Name Institute
 Bouvel Mathilde Institut für Mathematik Universität Zürich

Publications

Publication
Borga Jacopo (2021), Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels, in Random Structures & Algorithms, 59(3), 339-375.
Bassino Frédérique, Bouvel Mathilde, Féray Valentin, Gerin Lucas, Maazoun Mickaël, Pierrot Adeline (2021), Random cographs: Brownian graphon limit and asymptotic degree distribution, in Random Structures & Algorithms, rsa.21033-rsa.21033.
Borga Jacopo, Slivken Erik (2020), Square permutations are typically rectangular, in The Annals of Applied Probability, 30(5), 2196-2233.
Bassino Frédérique, Bouvel Mathilde, Féray Valentin, Gerin Lucas, Maazoun Mickaël, Pierrot Adeline (2020), Universal limits of substitution-closed permutation classes, in Journal of the European Mathematical Society, 22(11), 3565-3639.
Borga Jacopo, Bouvel Mathilde, Féray Valentin, Stufler Benedikt (2020), A decorated tree approach to random permutations in substitution-closed classes, in Electronic Journal of Probability, 25(none), 67.
Borga Jacopo (2020), Local convergence for permutations and local limits for uniform $$\rho$$-avoiding permutations with $$|\rho |=3$$, in Probability Theory and Related Fields, 176(1-2), 449-531.
BorgaJacopo, MaazounMickäel (2020), Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes, in Analysis of Algorithms 2020, Dagstuhl Research Online Publication Server, LIPIcs.
BorgaJacopo, DuchiEnrica, SlivkenErik, Almost square permutations are typically square, in Ann. Inst. H. Poincaré Probab. Statist., 1.

Collaboration

Group / person Country
Types of collaboration
 Oxford's Department of Statistics Great Britain and Northern Ireland (Europe)
 - in-depth/constructive exchanges on approaches, methods or results- Publication
 Univ. Zürich Switzerland (Europe)
 - in-depth/constructive exchanges on approaches, methods or results- Publication
 University of North Carolina Wilmington United States of America (North America)
 - in-depth/constructive exchanges on approaches, methods or results- Publication
 Univ. Paris 11, Univ. Paris 13, ENS of Lyon and Ecole Polytechnique France (Europe)
 - in-depth/constructive exchanges on approaches, methods or results- Publication

Scientific events

Active participation

Title Type of contribution Title of article or contribution Date Place Persons involved
 Bernoulli-IMS 10th WORLD CONGRESS in PROBABILITY and STATISTICS Talk given at a conference Universal phenomena for random constrained permutations 21.07.2021 Seoul National University, online conference, Korean Republic (South Korea) Borga Jacopo;
 8th European congress of Mathematics, Extremal and Probabilistic Combinatorics session Talk given at a conference Universal phenomena for random constrained permutations 24.06.2021 Portoroz, online conference, Slovenia Borga Jacopo;
 Permutation Patterns 2021 Talk given at a conference A probabilistic approach to generating trees 15.06.2021 University of Strathclyde, Glasgow (UK), online conference., Great Britain and Northern Ireland Borga Jacopo;
 Analysis of Algorithms 2021 Talk given at a conference Non-uniform permutations biased according to their records 14.06.2021 Klagenfurt, online meeting., Austria Bouvel Mathilde;
 Séminaire Philippe Flajolet Individual talk Graphon limit of random cographs 01.04.2021 Paris, France, online. , France Bouvel Mathilde;
 ALÉA 2021 Talk given at a conference Random permutations: A geometric point of view 16.03.2021 CIRM, Luminy (France), online conference., France Borga Jacopo;
 Workshop “Random Polymers and Networks”. Talk given at a conference Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes 07.09.2020 GESA, Iles de Porquerolles, France Borga Jacopo;
 Bernoulli-IMS One World Symposium 2020 (online). Talk given at a conference Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes, 24.08.2020 Bernoulli-IMS One World Symposium 2020 (online)., Switzerland Borga Jacopo;

Awards

Title Year
 Bernoulli Society New Researcher Award 2022. (Decided in 2021, awarded in 2022) 2021

Abstract

This research proposal fits into the topical area at the crossroad of combinatorics and discrete probability theory. It focuses mainly on pattern-avoiding permutations, which are popular objects in enumerative combinatorics whose study from a probabilistic point of view started very recently. It also considers related families of discrete objects, including the well-known hereditary graph classes. The main goal of this proposal is to revisit with a probabilistic purpose two classical tools for the enumeration of combinatorial objects (generating trees and substitution decomposition), thereby providing innovative methods for the study of random discrete structures. The project is organized along three research axes. Axis 1 is concerned with purely enumerative questions. The method of generating trees, combined with the kernel method for solving the resulting functional equations, is an established tool for solving some enumeration problems. But this method has its limitations, and we propose to widen its framework of applicability by generalizing it in two independent ways. First, we will develop a matrix version of the kernel method, with applications among others to the enumeration of all families of permutations defined by the avoidance of Baxter-like patterns. Second, we will define a generalized version of generating trees where the produced children can duplicate and mutate, which is expected to solve so far intractable problems on pattern-avoiding permutations. The breakthrough that can be expected from Axis 2 is the description of the graphon limit of many hereditary graph classes. We foresee that we will obtain limiting graphons that are essentially random and related to famous limits of discrete structures, like the Brownian excursion, exhibiting moreover universality phenomena for these graphon limits. The approach that we will take in addressing this original project combines tools developed for graphs in an algorithmic context (the modular and split decompositions of graphs) with a method we have recently introduced for finding limiting permuton of permutation classes via their substitution decomposition. In Axis 3, we return to generating trees, with the innovative idea to use them for describing limits of discrete structures. A first goal is the description of the local limits of families of pattern-avoiding permutations having a well-behaved generating tree. Thereby, we further develop the theory of local limits for permutations recently introduced by J. Borga (PhD student in the project), in analogy with its celebrated counterparts on trees and graphs. A key in achieving this goal is a Markov chain approach using an encoding of random permutations in such families by random walks in cones. A second goal is the discovery of new random limiting objects, in particular determining the permuton limit of Baxter permutations. This goal is topical in several ways. First, the discovery of new random limiting objects is one of the most challenging questions in discrete probability theory. Second, although their typical properties are almost unexplored for the moment, Baxter permutations are very popular in enumerative and bijective combinatorics, with a rich literature on the subject. To conclude, this research projects creates new bridges at the fruitful interface between combinatorics and probability theory. It proposes to define several new methods for the enumeration of discrete structures and for describing their limiting behavior, while offering concrete milestones solving such questions on well-known and topical combinatorial objects.
-