Factorizations of cycles and multi-noded rooted trees

DOI10.1007/S00373-013-1404-YMaRDI QIDQ2345521zbMATH OpenOpenAlexWikidataFDO

Authors Rosena R. X. Du, Fu Liu

Publication date 22 May 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

factorization graphHurwitz numbermulti-noded rooted tree

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Paths and cycles (05C38)

Abstract: In this paper, we study factorizations of cycles. The main result is that under certain condition, the number of ways to factor a $d$-cycle into a product of cycles of prescribed lengths is $d^{r-2}.$ To prove our result, we first define a new class of combinatorial objects, multi-noded rooted trees, which generalize rooted trees. We find the cardinality of this new class which with proper parameters is exactly $d^{r-2}.$ The main part of this paper is the proof that there is a bijection from factorizations of a $d$-cycle to multi-noded rooted trees via factorization graphs. This implies the desired formula. The factorization problem we consider has its origin in geometry, and is related to the study of a special family of Hurwitz numbers: pure-cycle Hurwitz numbers. Via the standard translation of Hurwitz numbers into group theory, our main result is equivalent to the following: when the genus is $0$ and one of the ramification indices is $d,$ the degree of the covers, the pure-cycle Hurwitz number is $d^{r-3},$ where $r$ is the number of branch points.

Recommendations

• Tree-like properties of cycle factorizations
• Factorization of de Bruijn digraphs by cycle-rooted trees
• scientific article; zbMATH DE number 1933250
• Trees, parking functions and factorizations of full cycles
• Semirotational tree factorizations of complete graphs
• Tree decompositions of multigraphs
• On tree factorizations of K_n
• Factorizations of \(K_{m,n}\) into spanning trees
• scientific article; zbMATH DE number 1076130
• scientific article; zbMATH DE number 874568

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 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• Labelled trees and factorizations of a cycle into transpositions
• Minimal Transitive Factorizations of Permutations into Cycles
• On multiplicities of the Lyashko-Looijenga mapping on discriminant strata
• The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group
• The irreducibility of certain pure-cycle Hurwitz spaces
• Transitive factorisations into transpositions and holomorphic mappings on the sphere
• Tree-like properties of cycle factorizations

Cited in

(5)

• Optimal factorizations of families of trees
• Labelled trees and factorizations of a cycle into transpositions
• On tree factorizations of K_n
• Random stable-type minimal factorizations of the \(n\)-cycle
• Minimal factorizations of a cycle: a multivariate generating function

This page was built for publication: Factorizations of cycles and multi-noded rooted trees

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