Loading [MathJax]/jax/output/HTML-CSS/jax.js

Mireille Bousquet-Mélou ; Julien Courtiel - Spanning forests in regular planar maps (conference version)

dmtcs:12808 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.12808
Spanning forests in regular planar maps (conference version)Conference paper

Authors: Mireille Bousquet-Mélou ORCID1; Julien Courtiel ORCID1

  • 1 Laboratoire Bordelais de Recherche en Informatique

We address the enumeration of p-valent planar maps equipped with a spanning forest, with a weight z per face and a weight u per component of the forest. Equivalently, we count regular maps equipped with a spanning tree, with a weight z per face and a weight μ:=u+1 per internally active edge, in the sense of Tutte. This enumeration problem corresponds to the limit q0 of the q-state Potts model on the (dual) p-angulations. Our approach is purely combinatorial. The generating function, denoted by F(z,u), is expressed in terms of a pair of series defined by an implicit system involving doubly hypergeometric functions. We derive from this system that F(z,u) is differentially algebraic, that is, satisfies a differential equation (in z) with polynomial coefficients in z and u. This has recently been proved for the more general Potts model on 3-valent maps, but via a much more involved and less combinatorial proof. For u1, we study the singularities of F(z,u) and the corresponding asymptotic behaviour of its nth coefficient. For u>0, we find the standard asymptotic behaviour of planar maps, with a subexponential factor n5/2. At u=0 we witness a phase transition with a factor n3. When u[1,0), we obtain an extremely unusual behaviour in n3/(logn)2. To our knowledge, this is a new ''universality class'' of planar maps.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: Exact and asymptotic enumeration,Spanning forests,Planar maps,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Arbres Aléatoires (continus) et Applications; Funder: French National Research Agency (ANR); Code: ANR-08-BLAN-0190

Consultation statistics

This page has been seen 126 times.
This article's PDF has been downloaded 131 times.