Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 19 mai 2020 à 18h00 en visioconférence, Colin Defant nous parlera de : Stack-sorting, troupes, and 3-stack sortable permutations

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.

 [vidéo]

Dernière modification : Thursday 21 November 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr