Mathematics – Combinatorics
Scientific paper
2009-09-09
Mathematics
Combinatorics
60 pages
Scientific paper
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 \chi_M(q) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q\not=0,4 is of the form 2+2 cos (j\pi/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,\nu), 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.
Bernardi Olivier
Bousquet-Mélou Mireille
No associations
LandOfFree
Counting colored planar maps: algebraicity results does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting colored planar maps: algebraicity results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting colored planar maps: algebraicity results will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-386169