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)Article

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 $\mu:=u+1$ per internally active edge, in the sense of Tutte. This enumeration problem corresponds to the limit $q \rightarrow 0$ 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 $\textit{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 $u \geq -1$, we study the singularities of $F(z,u)$ and the corresponding asymptotic behaviour of its $n^{\mathrm{th}}$ coefficient. For $u > 0$, we find the standard asymptotic behaviour of planar maps, with a subexponential factor $n^{-5/2}$. At $u=0$ we witness a phase transition with a factor $n^{-3}$. When $u \in[-1,0)$, we obtain an extremely unusual behaviour in $n^{-3}/(\log n)^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 92 times.
This article's PDF has been downloaded 75 times.