Asymptotic enumeration of orientations

Abstract : We find the asymptotic number of 2-orientations of quadrangulations with n inner faces, and of 3-orientations of triangulations with n inner vertices. We also find the asymptotic number of prime 2-orientations (no separating quadrangle) and prime 3-orientations (no separating triangle). The estimates we find are of the form c . n(-alpha)gamma(n), for suitable constants c, alpha, gamma with alpha = 4 for 2-orientations and alpha = 5 for 3-orientations. The proofs are based on singularity analysis of D-finite generating functions, using the Fuchsian theory of complex linear differential equations.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.249-262
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990467
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:51
Dernière modification le : mercredi 25 avril 2018 - 10:45:21
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:18:20

Fichier

1335-5088-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990467, version 1

Collections

Citation

Stefan Felsner, Eric Fusy, Marc Noy. Asymptotic enumeration of orientations. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.249-262. 〈hal-00990467〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

148