Alejandro Morales ; Ekaterina Vassilieva - Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution

dmtcs:2682 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2682
Bijective Enumeration of Bicolored Maps of Given Vertex Degree DistributionArticle

Authors: Alejandro Morales 1; Ekaterina Vassilieva 2

  • 1 Department of Mathematics [MIT]
  • 2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]

We derive a new formula for the number of factorizations of a full cycle into an ordered product of two permutations of given cycle types. For the first time, a purely combinatorial argument involving a bijective description of bicolored maps of specified vertex degree distribution is used. All the previous results in the field rely either partially or totally on a character theoretic approach. The combinatorial proof relies on a new bijection extending the one in [G. Schaeffer and E. Vassilieva. $\textit{J. Comb. Theory Ser. A}$, 115(6):903―924, 2008] that focused only on the number of cycles. As a salient ingredient, we introduce the notion of thorn trees of given vertex degree distribution which are recursive planar objects allowing simple description of maps of arbitrary genus. \par


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: bicolored maps,full cycle factorization,vertex degree distribution,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

8 Documents citing this article

Consultation statistics

This page has been seen 194 times.
This article's PDF has been downloaded 177 times.