Trajectories in random minimal transposition factorizations

MaRDI QIDQ5742626zbMATH OpenFDO

Authors Valentin Féray, Igor Kortchemski

Publication date 15 May 2019

Full work available at URL https://arxiv.org/abs/1810.07586, http://alea.impa.br/articles/v16/16-27.pdf

zbMATH Keywords

local limitsminimal factorizationsrandom trees

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Combinatorial probability (60C05) Functional limit theorems; invariance principles (60F17)

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.

Recommendations

• The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
• Degrees in random uniform minimal factorizations
• Random stable-type minimal factorizations of the \(n\)-cycle
• Tree-like properties of cycle factorizations
• Random generation and scaling limits of fixed genus factorizations into transpositions

Cites work

• A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
• Arbres et processus de Galton-Watson. (Trees and Galton-Watson processes)
• scientific article; zbMATH DE number 3149991 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1834045 (Why is no real title available?)
• Labelled trees and factorizations of a cycle into transpositions
• Local limits of conditioned Galton-Watson trees: the infinite spine case
• Non-crossing trees, quadrangular dissections, ternary trees, and duality-preserving bijections
• Probability on trees and networks
• Random graphs and complex networks. Volume 1
• Random sorting networks
• Random sorting networks: local statistics via random matrix laws
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• The Archimedean limit of random sorting networks
• The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
• The local limit of random sorting networks
• Tree-like properties of cycle factorizations

Cited in

(7)

• A geometric representation of fragmentation processes on stable trees
• Degrees in random uniform minimal factorizations
• Random generation and scaling limits of fixed genus factorizations into transpositions
• Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
• The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
• Random stable-type minimal factorizations of the \(n\)-cycle
• Random monotone factorisations of the cycle and their lamination process

This page was built for publication: Trajectories in random minimal transposition factorizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5742626)