Stefan Felsner ; Eric Fusy ; Marc Noy - Asymptotic enumeration of orientations

dmtcs:505 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 2 - https://doi.org/10.46298/dmtcs.505
Asymptotic enumeration of orientations

Authors: Stefan Felsner 1; Eric Fusy 2; Marc Noy 3

  • 1 Freie Universität Berlin
  • 2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
  • 3 Departament de Matemàtica Aplicada II

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.

https://doi.org/10.46298/dmtcs.505
Source: HAL:hal-00990467v1
Volume: Vol. 12 no. 2
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: Orientation,Quadrangulation,Triangulation,D-finite generating function,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 2005.13821
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.2005.13821
Source : ScholeXplorer IsRelatedTo DOI 10.5565/publmat6612213
Source : ScholeXplorer IsRelatedTo HANDLE 2117/375461
  • 2005.13821
  • 10.48550/arxiv.2005.13821
  • 2117/375461
  • 10.5565/publmat6612213
  • 10.5565/publmat6612213
On the expected number of perfect matchings in cubic planar graphs

Share and export

Consultation statistics

This page has been seen 225 times.
This article's PDF has been downloaded 182 times.