Permutation patterns and permutation classes ; Decomposition trees; Combinatorics; Discrete Mathematics; Permutations; Substitution decomposition; Combinatorial structure
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.
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.
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.
Albert Michael, Bouvel Mathilde (2015), A general theory of Wilf-equivalence for Catalan structures, in Electronic Journal of Combinatorics
, 22(4), P4.45.
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.
Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, Matteo Silimbani (2014), Combinatorics of non-ambiguous trees., in Advances in Applied Mathematics
, 56, 78-108.
Michael Albert, Mathilde Bouvel (2014), Operators of equivalent sorting power and related Wilf-equivalences., in Electronic Journal of Combinatorics
, 21(4), P4.11.
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.
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.