Laboratoire d'informatique de l'École polytechnique

Exposé par Paul Thevenin: «Geometry of random permutation factorizations»

Speaker: Paul Thevenin (CMAP)
Location: Salle Philippe Flajolet, LIX
Date: Mer. 6 nov. 2019, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Paul Thevenin (CMAP, École Polytechnique) nous parlera de Geometry of random permutation factorizations.

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé : We study random minimal factorizations of the n-cycle into transpositions, that is, factorizations of the cycle (12...n) into a product of n−1 transpositions. It is known that these factorizations are in bijection with Cayley trees of size n, and therefore that there are nn−2 of them. Moreover, they are naturally coded by sequences of sets of non-crossing chords in the unit disk. We establish the existence of a limit for such sets of chords, when they code a uniform random minimal factorization of the cycle. We show in particular how this random limit is naturally encoded in a Brownian excursion. The key tool of this study is an explicit bijection between minimal factorizations of the n-cycle and a family of trees with n labelled vertices. Finally, we explain how this framework can be extended to factorizations of (12...n) into cycles that are not necessarily transpositions, giving birth to new random structures.