A simple recurrence formula for the number of rooted maps on surfaces by edges and genus

Résumé : Nous établissons une formule de récurrence simple pour le nombre $Q_g^n$ de cartes enracinées de genre $g$ à $n$ arêtes. Cette formule est une conséquence relativement simple du fait que la série génératrice des cartes biparties est une solution de l’équation KP et d’une équation de Tutte, et elle était apparemment passée inaperçue jusque là. Elle donne de loin le moyen le plus rapide pour calculer ces nombres, en particulier quand $g$ est grand. La formule est d’apparence similaire à celle découverte par Goulden et Jackson pour les triangulations (quoique cette dernière ne repose pas sur une équation de Tutte additionnelle). Les deux formules ont une saveur très combinatoire, mais trouver une interprétation bijective reste un problème ouvert – mais si une telle interprétation existe, l’histoire des méthodes bijectives pour les cartes tendrait à montrer que le cas traité ici est plus facile pour commencer que celui des triangulations.
Type de document :
Communication dans un congrès
Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.573-584, 2014, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01207551
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 1 octobre 2015 - 09:28:15
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42
Document(s) archivé(s) le : samedi 2 janvier 2016 - 10:38:10

Fichier

dmAT0150.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01207551, version 1

Collections

Citation

Sean Carrell, Guillaume Chapuy. A simple recurrence formula for the number of rooted maps on surfaces by edges and genus. Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.573-584, 2014, DMTCS Proceedings. 〈hal-01207551〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

109