Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185374
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:06:24 AM
Last modification on : Thursday, March 5, 2020 - 6:31:07 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:08:54 AM

File

dmAK0155.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185374, version 1

Collections

Citation

Alejandro Morales, Ekaterina Vassilieva. Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.661-672. ⟨hal-01185374⟩

Share

Metrics

Record views

335

Files downloads

596