DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Font Size:  Small  Medium  Large

Spanning forests in regular planar maps

M. Bousquet-Mélou, J. Courtiel


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 &emm;tree,, with a weight z per face and a weight µ:=u+1 per &emm;internally active, edge, in the sense of Tutte. This enumeration problem corresponds to the limit q→0 of the q-state Potts model on the (dual) p-angulations. Our approach is purely combinatorial. The &gf;, 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 &emm;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≥-1, we study the singularities of F(z,u) and the corresponding asymptotic behaviour of its n^&hbox;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∈[-1,0), we obtain an extremely unusual behaviour in n-3/(logn)2. To our knowledge, this is a new ``universality class'' of planar maps.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional