Cycle factorizations and 1-faced graph embeddings

DOI10.1016/J.EJC.2009.04.005MaRDI QIDQ1041191zbMATH OpenOpenAlexWikidataFDO

Authors Dimitri Zvonkine, Yu Burman

Publication date 1 December 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Consider factorizations into transpositions of an n-cycle in the symmetric group S_n. To every such factorization we assign a monomial in variables w_{ij} that retains the transpositions used, but forgets their order. Summing over all possible factorizations of n-cycles we obtain a polynomial that happens to admit a closed expression. From this expression we deduce a formula for the number of 1-faced embeddings of a given graph.

Review text

To every factorization into transpositions of an \(n\)-cycle in the symmetric group \(S_n\), the authors assign a monomial in variables \(\omega_{ij}\) that retains the transpositions used, while forgetting their order. Summing over all possible factorizations of \(n\)-cycles, they obtain a polynomial having a closed expression and leading to a formula for the number of \(1\)-faced imbeddings of a given graph.

Recommendations

• Factorizations of large cycles in the symmetric group
• Short factorizations of permutations into transpositions
• Inequivalent transitive factorizations into transpositions
• Bijective enumeration of 3-factorizations of an \(N\)-cycle
• Bijections and symmetries for the factorizations of the long cycle

Cites work

• An algebro-geometric proof of Witten’s conjecture
• Enumeration of almost polynomial rational functions with given critical values
• Factorizations of large cycles in the symmetric group
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• scientific article; zbMATH DE number 3766017 (Why is no real title available?)
• scientific article; zbMATH DE number 51906 (Why is no real title available?)
• scientific article; zbMATH DE number 1066473 (Why is no real title available?)
• The Euler characteristic of the moduli space of curves
• The Gromov-Witten potential of a point, Hurwitz numbers, and Hodge integrals.
• Transitive factorisations into transpositions and holomorphic mappings on the sphere
• Tree-like properties of cycle factorizations
• Two-dimensional QCD is a string theory

Cited in

(7)

• Coxeter factorizations and the matrix tree theorem with generalized Jucys-Murphy weights
• Matrix-tree theorems and discrete path integration
• scientific article; zbMATH DE number 7664091 (Why is no real title available?)
• Coxeter factorizations with generalized Jucys–Murphy weights and Matrix‐Tree theorems for reflection groups
• Ribbon decomposition and twisted Hurwitz numbers
• Hurwitz numbers for the reflection groups \(B_n\) and \(D_n\)
• A duality for labeled graphs and factorizations with applications to graph embeddings and Hurwitz enumeration

This page was built for publication: Cycle factorizations and 1-faced graph embeddings

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