Record number :
Title of article :
Counting colored planar maps: Algebraicity results
Author/Authors :
Bernardi، نويسنده , , Olivier and Bousquet-Mélou، نويسنده , , Mireille، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
From page :
To page :
Abstract :
We address the enumeration of properly q-colored planar maps, or more precisely, the enumeration of rooted planar maps M weighted by their chromatic polynomial χ M ( q ) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q ≠ 0 , 4 is of the form 2 + 2 cos ( j π / m ) , for integers j and m. This includes the two integer values q = 2 and q = 3 . We extend this to planar maps weighted by their Potts polynomial P M ( q , ν ) , which counts all q-colorings (proper or not) by the number of monochromatic edges. We then prove similar results for planar triangulations, thus generalizing some results of Tutte which dealt with their proper q-colorings. In statistical physics terms, the problem we study consists in solving the Potts model on random planar lattices. From a technical viewpoint, this means solving non-linear equations with two “catalytic” variables. To our knowledge, this is the first time such equations are being solved since Tutteʼs remarkable solution of properly q-colored triangulations.
Keywords :
Enumeration , Colored planar maps , Algebraic generating functions , Tutte polynomial
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
Link To Document :