Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Generating functions ...
Conference paper

Generating functions of bipartite maps on orientable surfaces (extended abstract)

Guillaume Chapuy (1), Wenjie Fang ORCID (1)
(1) Laboratoire d'informatique Algorithmique : Fondements et Applications
Download article
Open on HAL
Imported on
November 21, 2016
Published on
December 31, 2014
Last modified on
March 31, 2025
Volume
DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Proceedings
DOI
10.46298/dmtcs.2531
License
Attribution 4.0 International (CC BY 4.0)
Indicators
695
Views
710
Downloads

Generating functions of bipartite maps on orientable surfaces (extended abstract)

Guillaume Chapuy (1), Wenjie Fang ORCID (1)
(1) Laboratoire d'informatique Algorithmique : Fondements et Applications
Abstract
English
We compute, for each genus $g$ ≥ 0, the generating function $L$<sub>$g$</sub> ≡ $L$<sub>$g$</sub>($t$;$p$<sub>1</sub>,$p$<sub>2</sub>,...) of (labelled) bipartite maps on the orientable surface of genus $g$, with control on all face degrees. We exhibit an explicit change of variables such that for each $g$, $L$<sub>$g$</sub> is a rational function in the new variables, computable by an explicit recursion on the genus. The same holds for the generating function $L$<sub>$g$</sub> of <i>rooted</i> bipartite maps. The form of the result is strikingly similar to the Goulden/Jackson/Vakil and Goulden/Guay-Paquet/Novak formulas for the generating functions of classical and monotone Hurwitz numbers respectively, which suggests stronger links between these models. Our result strengthens recent results of Kazarian and Zograf, who studied the case where the number of faces is bounded, in the equivalent formalism of <i>dessins d’enfants</i>. Our proofs borrow some ideas from Eynard’s “topological recursion” that he applied in particular to even-faced maps (unconventionally called “bipartite maps” in his work). However, the present paper requires no previous knowledge of this topic and comes with elementary (complex-analysis-free) proofs written in the perspective of formal power series.
French
Nous calculons, pour chaque genre $g$ ≥ 0, la série génératrice $L$<sub>$g$</sub> ≡ $L$<sub>$g$</sub>($t$;$p$<sub>1</sub>,$p$<sub>2</sub>,...) des cartes bipartites (étiquetées) sur la surface orientable de genre $g$, avec contrôle des degrés des faces. On exhibe un changement de variable explicite tel que pour tout $g$, $L$<sub>$g$</sub> est une fonction rationnelle des nouvelles variables, calculable par une récurrence explicite sur le genre. La même chose est vraie de la série génératrice $L$<sub>$g$</sub> des cartes biparties <i>enracinées</i>. La forme du résultat est similaire aux formules de Goulden/Jackson/Vakil et Goulden/Guay-Paquet/Novak pour les séries génératrices de nombres de Hurwitz classiques et monotones, respectivement, ce qui suggère des liens plus forts entre ces modèles. Notre résultat renforce des résultats récents de Kazarian et Zograf, qui étudient le cas où le nombre de faces est borné, dans le formalisme équivalent des <i>dessins d’enfants</i>. Nos démonstrations utilisent deux idées de la “récurrence topologique” d’Eynard, qu’il a appliquée notamment aux cartes paires (appelées de manière non-standard “cartes biparties” dans son travail). Cela dit, ce papier ne requiert pas de connaissance préliminaire sur ce sujet, et nos démonstrations (sans analyse complexe) sont écrites dans le language des séries formelles.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Enumeration
  • Maps on surfaces
  • Topological recursion
Preview
Loading PDF preview...