Résumé : West's stack-sorting map is a specific function that sends permutations to permutations. I will discuss a certain Decomposition Lemma that has led to several advances in the understanding of this function, including a polynomial-time algorithm for counting 3-stack-sortable permutations. We can generalize the Decomposition Lemma by considering special sets of binary plane trees called troupes. I will also mention recent progress concerning the average number of iterations of the stack-sorting map needed to sort a permutation.
|Dernière modification : Friday 15 May 2020||Contact : Cyril.Banderier at lipn.univ-paris13.fr|