Project

Back to overview

Permutation classes: from structure to combinatorial properties

Applicant Bouvel Mathilde
Number 151254
Funding scheme Marie Heim-Voegtlin grants
Research institution Institut für Mathematik Universität Zürich
Institution of higher education University of Zurich - ZH
Main discipline Mathematics
Start/End 01.06.2014 - 30.09.2016
Approved amount 168'559.00
Show all

All Disciplines (2)

Discipline
Mathematics
Information Technology

Keywords (7)

Permutation patterns and permutation classes ; Decomposition trees; Combinatorics; Discrete Mathematics; Permutations; Substitution decomposition; Combinatorial structure

Lay Summary (French)

Lead
L'ordre de motif dans les permutations et les classes de permutations qu'il définit constituent un thème de recherche important pour l'algorithmique et la combinatoire, et en particulier la combinatoire énumérative. Depuis la définition de ces concepts il y a 40 ans, on recense de nombreux résultats sur l'énumération de classes particulières de permutations. En 2004, la preuve par Marcus et Tardos de la conjecture de Stanley-Wilf a ouvert une nouvelle perspective dans l'étude des classes de permutations. Il ne s'agit plus de démontrer des résultats concernant une classe particulière, mais d'obtenir des résultats, peut-être moins précis, mais qui décrivent des propriétés communes à toutes les classes de permutations, ou à de grandes familles de telles classes.
Lay summary

Ce projet propose plusieurs directions pour obtenir de tels résultats généraux sur les classes de permutations, qui reposent sur des structures (via des arbres de décompositions, des diagrammes, ou des graphes) sous-jacentes aux permutations. Un premier aspect de notre étude concerne la description de la forme "moyenne" des permutations aléatoires dans une classe. Une seconde thématique se concentre sur les classes possédant la même séquence d'énumération, et cherche à obtenir une explication globale pour bon nombre de ces coïncidences d'énumération. Le troisième axe de recherche, plus prospectif, cherche à transporter des problèmes et résultats sur l'ordre de motif dans les permutations à l'ordre de sous-graphe induit dans les graphes, et vice-versa.

La richesse de ce projet est de créer des liens entre la recherche sur les classes de permutations et d'autres domaines des mathématiques discrètes (probabilités, théorie des graphes) pour découvrir de nouvelles propriétés combinatoires générales de ces classes.
Direct link to Lay Summary Last update: 05.05.2014

Responsible applicant and co-applicants

Employees

Publications

Publication
Permutation classes and polyomino classes with excluded submatrices.
Daniela Battaglino, Mathilde Bouvel, Andrea Frosini, Simone Rinaldi (2017), Permutation classes and polyomino classes with excluded submatrices., in Mathematical Structures in Computer Science, 27(2), 157-1183.
Analysis of Algorithms for Permutations Biased by Their Number of Records
Auger Nicolas, Bouvel Mathilde, Nicaud Cyril, Pivoteau Carine (2016), Analysis of Algorithms for Permutations Biased by Their Number of Records, in Analysis of Algorithms 2016, Krakow, PolandProceedings published electronically, http://www.aofa.tcs.uj.edu.pl/accepted-papers.html.
Slicings of parallelogram polyominoes, or how Baxter and Schröder can be reconciled
Bouvel Mathilde, Guerrini Veronica, Rinaldi Simone (2016), Slicings of parallelogram polyominoes, or how Baxter and Schröder can be reconciled, in FPSAC 2016, Vancouver, Canada.
A general theory of Wilf-equivalence for Catalan structures
Albert Michael, Bouvel Mathilde (2015), A general theory of Wilf-equivalence for Catalan structures, in Electronic Journal of Combinatorics, 22(4), P4.45.
An algorithm for deciding the finiteness of the number of simple permutations in permutation classes.
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Dominique Rossin (2015), An algorithm for deciding the finiteness of the number of simple permutations in permutation classes., in Advances in Applied Mathematics, 64, 124-200.
Combinatorics of non-ambiguous trees.
Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Matteo Silimbani (2014), Combinatorics of non-ambiguous trees., in Advances in Applied Mathematics, 56, 78-108.
Operators of equivalent sorting power and related Wilf-equivalences.
Michael Albert, Mathilde Bouvel (2014), Operators of equivalent sorting power and related Wilf-equivalences., in Electronic Journal of Combinatorics, 21(4), P4.11.
Refined enumeration of permutations sorted with two stacks and a D_8-symmetry.
Mathilde Bouvel, Olivier Guibert (2014), Refined enumeration of permutations sorted with two stacks and a D_8-symmetry., in Annals of Combinatorics, 18(2), 199-232.

Collaboration

Group / person Country
Types of collaboration
Otago University, dpt of computer science New Zealand (Oceania)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
PHC Germaine de Staël 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
Conference Permutation Patterns 2016 Talk given at a conference The Brownian limit of separable permutations 27.06.2016 Howard University, Washington DC, United States of America Bouvel Mathilde;
Workshop Pattern Avoidance and Genome Sorting Talk given at a conference Decomposition trees of permutations, and how to use them for a (realistic ?) study of perfect sorting by reversals 14.02.2016 Schloss Dagstuhl, Germany Bouvel Mathilde;
Séminaire Lotharingien de Combinatoire Talk given at a conference A general theory of Wilf-equivalence for Catalan structures 07.09.2014 Strobl, Austria Bouvel Mathilde;
Conference Permutation Patterns 2014 Talk given at a conference A general theory of Wilf-equivalence for permutation classes Av(231; p), and other Catalan structures 07.07.2014 Johnson City, USA, United States of America Bouvel Mathilde;


Awards

Title Year
Marie Heim-Vögtlin prize 2017. 2017

Associated projects

Number Title Start Funding scheme
172536 Several aspects of the study of non-uniform random permutations 01.09.2017 Project funding (Div. I-III)

Abstract

Permutation patterns and permutation classes have been defined in the seventies, in connection with partial sorting algorithms. Enumerative combinatorics soon became interested in this topic, and the enumeration of many specific permutation classes has been achieved in the literature.For about a decade, another and more general perspective in the research on permutation classes has emerged. It is not interested in the study of specific classes, but rather focuses on describing combinatorial properties shared by families of permutation classes, as large as possible. The proof of the Stanley-Wilf conjecture, stating that every permutation class has an enumerating sequence bounded by c^n for some constant c, is certainly the first and emblematic result of this line of research.In my project, I offer several directions for finding general combinatorial properties of permutation classes. They all rely on the idea of taking advantage of the structure of permutation classes, either from a graphical point of view or through their so-called decomposition trees.First, I shall be interested in large random permutations taken uniformly in permutation classes. It is striking to notice that almost nothing is known on the subject. Using decomposition trees, I have developed with some co-authors an algorithmic chain that produces, for every class C satisfying a rather general condition, a combinatorial specification for C, and a random sampler for C. I believe this provides both a strong theoretical basis for studying random permutations in permutation classes, and a computational tool to investigate the subject.Second, in recent work we have defined families of bijections between permutation classes. These bijections are built from the graphical structure of the permutations in these classes. We have obtained several new enumerative results, under the form of Wilf-equivalences. We believe that a more general study of graphically-oriented bijections (of which our first result is only an example), may provide similar results in a more general setting.Third, I would like to create an interaction between the study of permutation classes and that of induced subgraph ideals in graph theory. Their definitions are very similar (downward closed families of combinatorial objects defined by excluded substructures), however the problems investigated in both communities are of different nature. In particular, inspired by some recent results on graphs, I would like to consider the following question: describe properties of permutation classes that do not entirely contain other classical permutation classes. In the other direction, studying conjectures about induced subgraph ideals with the point of view and methods from the study of permutation classes may provide new insight on them, and hopefully hints towards their proofs.To conclude, my project explore new directions for finding general combinatorial results on permutation classes. It also creates links between research on permutation classes and other fields (probability theory, graph theory), that are original and promise to be fruitful.
-