Discrete Mathematics & Theoretical Computer Science |

- 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.

Source: HAL:hal-00851354v1

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]

This page has been seen 28 times.

This article's PDF has been downloaded 17 times.