Mathematics – Combinatorics
Scientific paper
2010-06-25
Advances in Applied Mathematics, 47(4):874-893 (2011)
Mathematics
Combinatorics
Scientific paper
A unicellular map, or one-face map, is a graph embedded in an orientable surface such that its complement is a topological disk. In this paper, we give a new viewpoint to the structure of these objects, by describing a decomposition of any unicellular map into a unicellular map of smaller genus. This gives a new combinatorial identity for the number $\epsilon_g(n)$ of unicellular maps of size $n$ and genus $g$. Contrarily to the Harer-Zagier recurrence formula, this identity is recursive in only one parameter (the genus). Iterating the construction gives an explicit bijection between unicellular maps and plane trees with distinguished vertices, which gives a combinatorial explanation (and proof) of the fact that $\epsilon_g(n)$ is the product of the $n$-th Catalan number by a polynomial in $n$. The combinatorial interpretation also gives a new and simple formula for this polynomial. Variants of the problem are considered, like bipartite unicellular maps, or unicellular maps with cubic vertices only.
No associations
LandOfFree
A new combinatorial identity for unicellular maps, via a direct bijective approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A new combinatorial identity for unicellular maps, via a direct bijective approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new combinatorial identity for unicellular maps, via a direct bijective approach will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-310669