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

dmtcs:505 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 2 -
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.

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

Consultation statistics

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