Tree-like properties of cycle factorizations

DOI10.1006/JCTA.2001.3230zbMATH Open0992.05002arXivmath/0106039OpenAlexW2050823015WikidataQ114234205 ScholiaQ114234205MaRDI QIDQ1601424FDOQ1601424

Authors: I. P. Goulden, Alexander Yong 

Publication date: 30 August 2002

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We provide a bijection between the set of factorizations, that is, ordered (n-1)-tuples of transpositions in ${mathcalS}_n$ whose product is (12...n), and labelled trees on $n$ vertices. We prove a refinement of a theorem of D'{e}nes that establishes new tree-like properties of factorizations. In particular, we show that a certain class of transpositions of a factorization correspond naturally under our bijection to leaf edges of a tree. Moreover, we give a generalization of this fact.

Full work available at URL: https://arxiv.org/abs/math/0106039

Recommendations

• A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
• scientific article; zbMATH DE number 6007658
• scientific article; zbMATH DE number 798638
• Transitive cycle factorizations and prime parking functions
• Labelled trees and factorizations of a cycle into transpositions

zbMATH Keywords

factorizationbijectionHurwitz numberstranspositionCayley formula

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Symmetric groups (20B30)

Cites Work

• Principles of combinatorics
• Transitive factorisations into transpositions and holomorphic mappings on the sphere
• A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
• Labelled trees and factorizations of a cycle into transpositions
• The Gromov-Witten potential of a point, Hurwitz numbers, and Hodge integrals.
• Title not available (Why is that?)
• Stable maps and branch divisors
• Title not available (Why is that?)
• On Hurwitz numbers and Hodge integrals
• Topological classification of trigonometric polynomials and combinatorics of graphs with an equal number of vertices and edges
• Title not available (Why is that?)

Cited In (29)

• A combinatorial interpretation of the bijection of Goulden and Yong
• Random generation and scaling limits of fixed genus factorizations into transpositions
• Spanning hypertrees, vertex tours and meanders
• A geometric representation of fragmentation processes on stable trees
• Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
• Exceptional sequences over path algebras of type \(A_n\) and non-crossing spanning trees.
• Transitive cycle factorizations and prime parking functions
• Planted Brussels Sprouts (after Ji-Propp)
• Random stable-type minimal factorizations of the \(n\)-cycle
• A duality for labeled graphs and factorizations with applications to graph embeddings and Hurwitz enumeration
• Trajectories in random minimal transposition factorizations
• The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
• Trees, parking functions and factorizations of full cycles
• Annular noncrossing permutations and minimal transitive factorizations
• The number of prefixes of minimal factorisations of a cycle
• Combinatorial flip actions and Gelfand pairs for affine Weyl groups
• Factorizations of cycles and multi-noded rooted trees
• A new bijection between ordered trees and legal bracketings
• Cycle factorizations and 1-faced graph embeddings
• A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
• \(k\)-factorizations of the full cycle and generalized Mahonian statistics on \(k\)-forests
• Degrees in random uniform minimal factorizations
• On maximal chains in the non-crossing partition lattice
• Labelled trees and factorizations of a cycle into transpositions
• Combinatorics of exceptional sequences in type A
• Ribbon decomposition and twisted Hurwitz numbers
• On tree factorizations of K_n
• Some factorisations counted by Catalan numbers
• Parking functions, tree depth and factorizations of the full cycle into transpositions

This page was built for publication: Tree-like properties of cycle factorizations

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