Geometry of random permutation factorizations

-- Paul Thevenin (CMAP, École Polytechnique)

Time: 10:30 -- Location: Salle Philippe Flajolet du LIX

We study random minimal factorizations of the \(n\)-cycle into transpositions, that is, factorizations of the cycle \((1 2...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 \(n^{n-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 \((1 2 ... n)\) into cycles that are not necessarily transpositions, giving birth to new random structures.

Category: seminars
Tags: Combi seminar combinatorics