Trajectories in random minimal transposition factorizations
Preprint
Abstract
We study random typical minimal factorizations of the $n$-cycle, which are factorizations of $(1, \ldots,n)$ as a product of $n-1$ transpositions, chosen uniformly at random. Our main result is, roughly speaking, a local convergence theorem for the trajectories of finitely many points in the factorization. The main tool is an encoding of the factorization by an edge and vertex-labelled tree, which is shown to converge to Kesten's infinite Bienaym\'e-Galton-Watson tree with Poisson offspring distribution, uniform i.i.d. edge labels and vertex labels obtained by a local exploration algorithm.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The Archimedean limit of random sorting networksJournal of the American Mathematical Society, 2021
- Non-crossing Trees, Quadrangular Dissections, Ternary Trees, and Duality-Preserving BijectionsAnnals of Combinatorics, 2021
- The local limit of random sorting networksAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques, 2019
- Random Graphs and Complex Networks2016
- Probability on Trees and Networks2016
- Simply generated trees, conditioned Galton–Watson trees, random allocations and condensationProbability Surveys, 2012
- Random sorting networksAdvances in Mathematics, 2007
- Tree-like Properties of Cycle FactorizationsJournal of Combinatorial Theory, Series A, 2002
- Labelled trees and factorizations of a cycle into transpositionsDiscrete Mathematics, 1993
- A Solution to a Problem of Dénes: a Bijection Between Trees and Factorizations of Cyclic PermutationsEuropean Journal of Combinatorics, 1989