Spanning forests in regular planar maps

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:135

Article

Bousquet-Melou, Mireille¹  Courtiel, Julien¹ 

[1] Univ Bordeaux, UMR 5800, LaBRI, CNRS, F-33405 Talence, France

关键词: Enumeration;    Planar maps;    Tutte polynomial;    Spanning forests;   

DOI  :  10.1016/j.jcta.2015.04.002

来源: Elsevier

【 摘 要 】

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 connected component of the forest. Equivalently, we count p-valent 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; or the (dual) p-angulations equipped with a recurrent sandpile configuration, with a weight z per vertex and a variable mu := u + 1 that keeps track of the level of the configuration. This enumeration problem also corresponds to the limit q -> 0 of the q-state Potts model on p-angulations. Our approach is purely combinatorial. The associated generating function, denoted F(z, u), is expressed in terms of a pair of series defined implicitly by a system involving doubly hypergeometric series. We derive from this system that F(z, u) is differentially algebraic in z, that is, satisfies a differential equation in z with polynomial coefficients in z and u. This has recently been proved to hold 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 nth coefficient. For u > 0, we find the standard behaviour of planar maps, with a subexponential term in n(-5/2). At u = 0 we witness a phase transition with a term n(-3). When u is an element of [-1,0), we obtain an extremely unusual behaviour in n(-3)(1nn)(-2). To our knowledge, this is a new universality class for planar maps. We analyze the phase transition at u = 0 in terms of the sandpile model on large maps, and find it to be of infinite order. (C) 2015 Elsevier Inc. All rights reserved.

【 授权许可】

Free