Simple recurrence formulas to count maps on orientable surfaces
| Autor: | Guillaume Chapuy, Sean R. Carrell |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Projet Émergences Ville de Paris 'Combinatoire à Paris', ANR-12-JS02-0001,CARTAPLUS,Combinatoire des cartes et applications(2012) |
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Polynomial Generating function Kadomtsev–Petviashvili equation Theoretical Computer Science Interpretation (model theory) Combinatorics Computational Theory and Mathematics Simple (abstract algebra) Genus (mathematics) [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Bipartite graph Bijection FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series A Journal of Combinatorial Theory, Series A, Elsevier, 2015, 133, pp.58--75. ⟨10.1016/j.jcta.2015.01.005⟩ |
| ISSN: | 0097-3165 1096-0899 |
| DOI: | 10.48550/arxiv.1402.6300 |
| Popis: | We establish a simple recurrence formula for the number $Q_g^n$ of rooted orientable maps counted by edges and genus. We also give a weighted variant for the generating polynomial $Q_g^n(x)$ where $x$ is a parameter taking the number of faces of the map into account, or equivalently a simple recurrence formula for the refined numbers $M_g^{i,j}$ that count maps by genus, vertices, and faces. These formulas give by far the fastest known way of computing these numbers, or the fixed-genus generating functions, especially for large $g$. In the very particular case of one-face maps, we recover the Harer-Zagier recurrence formula. Our main formula is a consequence of the KP equation for the generating function of bipartite maps, coupled with a Tutte equation, and it was apparently unnoticed before. It is similar in look to the one discovered by Goulden and Jackson for triangulations, and indeed our method to go from the KP equation to the recurrence formula can be seen as a combinatorial simplification of Goulden and Jackson's approach (together with one additional combinatorial trick). All these formulas have a very combinatorial flavour, but finding a bijective interpretation is currently unsolved. Comment: Version 3: We changed the title once again. We also corrected some misprints, gave another equivalent formulation of the main result in terms of vertices and faces (Thm. 5), and added complements on bivariate generating functions. Version 2: We extended the main result to include the ability to track the number of faces. The title of the paper has been changed accordingly |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect