Tree-like properties of cycle factorizations
From MaRDI portal
Publication:1601424
Abstract: We provide a bijection between the set of factorizations, that is, ordered (n-1)-tuples of transpositions in whose product is (12...n), and labelled trees on 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.
This paper provides a new bijection between the set of factorizations of the permutation \((123\dots n)\) into an ordered \((n-1)\)-tuple of transpositions, and labelled trees on \(n\) vertices. Unlike earlier bijections, the new bijection connects some natural objects to natural objects, like transpositions of consecutive pairs correspond to leaves in the tree. This new bijection may help in the combinatorial understanding of minimal transitive factorization of permutations.
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
Cites work
- A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
- scientific article; zbMATH DE number 3149991 (Why is no real title available?)
- scientific article; zbMATH DE number 3957110 (Why is no real title available?)
- scientific article; zbMATH DE number 1504631 (Why is no real title available?)
- Labelled trees and factorizations of a cycle into transpositions
- On Hurwitz numbers and Hodge integrals
- Principles of combinatorics
- Stable maps and branch divisors
- The Gromov-Witten potential of a point, Hurwitz numbers, and Hodge integrals.
- Topological classification of trigonometric polynomials and combinatorics of graphs with an equal number of vertices and edges
- Transitive factorisations into transpositions and holomorphic mappings on the sphere
Cited in
(33)- Cycle factorizations and 1-faced graph embeddings
- A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
- Transitive cycle factorizations and prime parking functions
- A new bijection between ordered trees and legal bracketings
- Exceptional sequences over path algebras of type A_n and non-crossing spanning trees.
- 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
- Combinatorial flip actions and Gelfand pairs for affine Weyl groups
- Trees, parking functions and factorizations of full cycles
- The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
- Factorizations of cycles and multi-noded rooted trees
- Labelled trees and factorizations of a cycle into transpositions
- Annular noncrossing permutations and minimal transitive factorizations
- On maximal chains in the non-crossing partition lattice
- Some factorisations counted by Catalan numbers
- The number of prefixes of minimal factorisations of a cycle
- On tree factorizations of Kn
- Planted Brussels Sprouts (after Ji-Propp)
- Random stable-type minimal factorizations of the \(n\)-cycle
- Parking functions, tree depth and factorizations of the full cycle into transpositions
- A combinatorial interpretation of the bijection of Goulden and Yong
- Trajectories in random minimal transposition factorizations
- \(k\)-factorizations of the full cycle and generalized Mahonian statistics on \(k\)-forests
- Ribbon decomposition and twisted Hurwitz numbers
- Spanning hypertrees, vertex tours and meanders
- A duality for labeled graphs and factorizations with applications to graph embeddings and Hurwitz enumeration
- Combinatorics of exceptional sequences in type A
- Random monotone factorisations of the cycle and their lamination process
- An elaborate new proof of Cayley's formula
- Exceptional sequences and rooted labeled forests
- Lyashko-Looijenga morphisms and primitive factorizations of Coxeter elements
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)
