Counting colored planar maps: algebraicity results
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2009
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916968302379008 |
|---|---|
| author | Bernardi, Olivier Bousquet-Mélou, Mireille |
| author_facet | Bernardi, Olivier Bousquet-Mélou, Mireille |
| contents | 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\not=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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_0909_1695 |
| institution | arXiv |
| publishDate | 2009 |
| record_format | arxiv |
| spellingShingle | Counting colored planar maps: algebraicity results Bernardi, Olivier Bousquet-Mélou, Mireille Combinatorics 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\not=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. |
| title | Counting colored planar maps: algebraicity results |
| topic | Combinatorics |
| url | https://arxiv.org/abs/0909.1695 |