The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees

[La géométrie des factorisations minimales aléatoires d’un long cycle via des arbres aléatoires bitype doublement conditionnés]

Féray, Valentin¹ ; Kortchemski, Igor²

¹ Universität Zürich, Institut für Mathematik, Winterthurerstr. 190, 8057 Zürich (Switzerland)
² CNRS & CMAP, École polytechnique, route de Saclay 91128 Palaiseau Cedex (France)

Annales Henri Lebesgue, Tome 1 (2018), pp. 149-226

Abstract (VO)

We study random typical minimal factorizations of the $n$-cycle into transpositions, which are factorizations of $(1,...,n)$ as a product of $n-1$ transpositions. By viewing transpositions as chords of the unit disk and by reading them one after the other, one obtains a sequence of increasing laminations of the unit disk (i.e. compact subsets of the unit disk made of non-intersecting chords).

When an order of $\sqrt{n}$ consecutive transpositions have been read, we establish, roughly speaking, that a phase transition occurs and that the associated laminations converge to a new one-parameter family of random laminations, constructed from excursions of specific Lévy processes.

Our main tools involve coding random minimal factorizations by conditioned two-type Bienaymé–Galton–Watson trees. We establish in particular limit theorems for two-type BGW trees conditioned on having given numbers of vertices of both types, and with an offspring distribution depending on the conditioning size. We believe that this could be of independent interest.

Résumé

Nous étudions les factorisations minimales aléatoires d’un $n$-cycle en transpositions, c’est-à-dire les décompositions de $(1,\cdots ,n)$ comme un produit de $n-1$ transpositions. En représentant les transpositions comme des cordes du disque unité et en les lisant les unes après les autres, on obtient une suite croissantes de laminations du disque unité (i.e. de sous-ensembles compacts du disque unité constitués de cordes ne se croisant pas).

Quand le nombre de transpositions lues est de l’ordre $\sqrt{n}$, nous établissons l’existence d’une transition de phase et la convergence des laminations associées vers une nouvelle famille de laminations aléatoires à un paramètre, construites à partir de processus de Lévy.

Notre outil principle est le codage de ces factorisations minimal aléatoires par des arbres de Bienaymé–Galton–Watson bitype conditionnés. En particulier, nous obtenons des théorèmes limites pour de tels arbres, conditionnés à avoir un nombre fixe de nœuds de chaque couleur, et dont la loi de reproduction dépend de la taille à laquelle on conditionne. Nous pensons que ce résultat est aussi intéressant en lui-même.

Détail

Reçu le : 2018-01-11
Accepté le : 2018-11-21
Publié le : 2019-03-29
DOI : 10.5802/ahl.5

Classification : 60C05, 60B15
Keywords: Permutation factorisation, random trees, non-crossing partitions, Lévy processes, Brownian triangulation

Licence : CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits