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.