Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution

Abstract

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

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]