Counting colored planar maps: algebraicity results. (English) Zbl 1223.05123
Summary: 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\neq 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.
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.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C15 | Coloring of graphs and hypergraphs |
Software:
gfunReferences:
| [1] | Banderier, C.; Bousquet-Mélou, M.; Denise, A.; Flajolet, P.; Gardy, D.; Gouyou-Beauchamps, D., Generating functions for generating trees, Discrete Math., 246, 1-3, 29-55 (2002) · Zbl 0997.05007 |
| [2] | Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci., 281, 1-2, 37-80 (2002) · Zbl 0996.68126 |
| [3] | Baxter, R. J., Dichromatic polynomials and Potts models summed over rooted maps, Ann. Comb., 5, 1, 17-36 (2001) · Zbl 0983.05041 |
| [4] | Bender, E. A.; Canfield, E. R., The number of degree-restricted rooted maps on the sphere, SIAM J. Discrete Math., 7, 1, 9-15 (1994) · Zbl 0794.05048 |
| [5] | Beraha, S.; Kahane, J.; Weiss, N. J., Limits of chromatic zeros of some families of maps, J. Combin. Theory Ser. B, 28, 1, 52-65 (1980) · Zbl 0433.05030 |
| [6] | Bernardi, O., Bijective counting of tree-rooted maps and shuffles of parenthesis systems, Electron. J. Combin., 14, 1 (2007), Research Paper 9, 36 pp. (electronic) · Zbl 1115.05002 |
| [7] | Bernardi, O.; Fusy, É., A bijection for triangulations, quadrangulations, pentagulations, etc. (2010) · Zbl 1232.05019 |
| [8] | Bollobás, B., Modern Graph Theory, Grad. Texts in Math., vol. 184 (1998), Springer-Verlag: Springer-Verlag New York · Zbl 0902.05016 |
| [9] | Boulatov, D. V.; Kazakov, V. A., The Ising model on a random planar lattice: the structure of the phase transition and the exact critical exponents, Phys. Lett. B, 186, 3-4, 379-384 (1987) |
| [10] | Bousquet-Mélou, M., Four classes of pattern-avoiding permutations under one roof: generating trees with two labels, Electron. J. Combin., 9, 2 (2002/2003), Research Paper 19, 31 pp. (electronic) · Zbl 1031.05006 |
| [11] | Bousquet-Mélou, M., Walks in the quarter plane: Krewerasʼ algebraic model, Ann. Appl. Probab., 15, 2, 1451-1491 (2005) · Zbl 1064.05010 |
| [12] | Bousquet-Mélou, M.; Jehanne, A., Planar maps and algebraic series: a generalization of the quadratic method, J. Combin. Theory Ser. B, 96, 623-672 (2006) · Zbl 1099.05043 |
| [13] | Bousquet-Mélou, M.; Mishna, M., Walks with small steps in the quarter plane, Contemp. Math., 520, 1-40 (2010) · Zbl 1209.05008 |
| [14] | Bousquet-Mélou, M.; Petkovšek, M., Linear recurrences with constant coefficients: the multivariate case, Discrete Math., 225, 1-3, 51-75 (2000) · Zbl 0963.05005 |
| [15] | Bousquet-Mélou, M.; Schaeffer, G., The degree distribution of bipartite planar maps: applications to the Ising model, (Eriksson, K.; Linusson, S., Formal Power Series and Algebraic Combinatorics (2003), Vadstena: Vadstena Sweden), 312-323 |
| [16] | Bouttier, J.; Di Francesco, P.; Guitter, E., Census of planar maps: from the one-matrix model solution to a combinatorial proof, Nuclear Phys. B, 645, 3, 477-499 (2002) · Zbl 0999.05052 |
| [17] | Bouttier, J.; Di Francesco, P.; Guitter, E., Planar maps as labeled mobiles, Electron. J. Combin., 11, 1 (2004), Research Paper 69, 27 pp. (electronic) · Zbl 1060.05045 |
| [18] | Chapuy, G., Asymptotic enumeration of constellations and related families of maps on orientable surfaces, Combin. Probab. Comput., 18, 4, 477-516 (2009) · Zbl 1221.05204 |
| [19] | Chassaing, P.; Schaeffer, G., Random planar lattices and integrated superBrownian excursion, Probab. Theory Related Fields, 128, 2, 161-212 (2004) · Zbl 1041.60008 |
| [20] | Daul, J.-M., \(q\)-States Potts model on a random planar lattice |
| [21] | Eynard, B.; Bonnet, G., The Potts-\(q\) random matrix model: loop equations, critical exponents, and rational case, Phys. Lett. B, 463, 2-4, 273-279 (1999) · Zbl 1037.82522 |
| [22] | Eynard, B.; Kristjansen, C., Exact solution of the \(O(n)\) model on a random lattice, Nuclear Phys. B, 455, 577-618 (1995) · Zbl 0925.81129 |
| [23] | Eynard, B.; Kristjansen, C., More on the exact solution of the \(O(n)\) model on a random lattice and an investigation of the case \(n > 2\), Nuclear Phys. B, 466, 463-487 (1996) · Zbl 1002.81521 |
| [24] | Eynard, B.; Zinn-Justin, J., The \(O(n)\) model on a random surface: critical points and large order behaviour, Nuclear Phys. B, 386, 558-591 (1992) |
| [25] | Fendley, P.; Krushkal, V., Tutte chromatic identities from the Temperley-Lieb algebra, Geom. Topol., 13, 2, 709-741 (2009) · Zbl 1184.57002 |
| [26] | Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci., 49, 2-3, 283-309 (1987) · Zbl 0612.68069 |
| [27] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 |
| [28] | Fortuin, C. M.; Kasteleyn, P. W., On the random cluster model: I. Introduction and relation to other models, Physica, 57, 536-564 (1972) |
| [29] | Fusy, É.; Poulalhon, D.; Schaeffer, G., Dissections and trees, with applications to optimal mesh encoding and to random sampling, ACM Trans. Algorithms, 4, 2 (2008), Art. 19 · Zbl 1451.05230 |
| [30] | Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), A Wiley-Interscience Publication, John Wiley & Sons Inc.: A Wiley-Interscience Publication, John Wiley & Sons Inc. New York · Zbl 0519.05001 |
| [31] | Greene, C.; Zaslavsky, T., On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc., 280, 1, 97-126 (1983) · Zbl 0539.05024 |
| [32] | Jacobsen, J. L.; Richard, J.-F.; Salas, J., Complex-temperature phase diagram of Potts and RSOS models, Nuclear Phys. B, 743, 3, 153-206 (2006) · Zbl 1214.82017 |
| [33] | Jacobsen, J. L.; Salas, J., Transfer matrices and partition-function zeros for antiferromagnetic Potts models. II. Extended results for square-lattice chromatic polynomial, J. Stat. Phys., 104, 3-4, 701-723 (2001) · Zbl 1100.82506 |
| [34] | Lass, B., Orientations acycliques et le polynôme chromatique, European J. Combin., 22, 8, 1101-1123 (2001) · Zbl 0990.05063 |
| [35] | Liu, Y., Chromatic sum equations for rooted planar maps, (Proceedings of the Fifteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 45. Proceedings of the Fifteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 45, Baton Rouge, LA, 1984 (1984)), 275-280 · Zbl 0559.05028 |
| [36] | Liu, Y., On chromatic and dichromatic sum equations, Discrete Math., 84, 169-179 (1990) · Zbl 0721.05022 |
| [37] | Martin, P. P., The Potts model and the Beraha numbers, J. Phys. A, 20, 6, L399-L403 (1987) |
| [38] | Mishna, M.; Rechnitzer, A., Two non-holonomic lattice walks in the quarter plane, Theoret. Comput. Sci., 410, 38-40, 3616-3630 (2009) · Zbl 1228.05038 |
| [39] | Mullin, R. C., On the enumeration of tree-rooted maps, Canad. J. Math., 19, 174-183 (1967) · Zbl 0148.17705 |
| [40] | Mullin, R. C.; Nemeth, E.; Schellenberg, P. J., The enumeration of almost cubic maps, (Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, Louisiana State Univ.. Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, LA, 1970 (1970), Louisiana State Univ.: Louisiana State Univ. Baton Rouge, LA), 281-295 · Zbl 0223.05117 |
| [41] | Odlyzko, A. M.; Richmond, L. B., A differential equation arising in chromatic sum theory, (Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 40. Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 40, Boca Raton, FL, 1983 (1983)), 263-275 · Zbl 0535.05035 |
| [42] | Prodinger, H., The kernel method: a collection of examples, Sém. Lothar. Combin., 50 (2003/2004), Art. B50f, 19 pp. (electronic) · Zbl 1063.05011 |
| [43] | Saleur, H., Zeroes of chromatic polynomials: a new approach to Beraha conjecture using quantum groups, Comm. Math. Phys., 132, 3, 657-679 (1990) · Zbl 0708.05024 |
| [44] | Salvy, B.; Zimmermann, P., Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software, 20, 2, 163-177 (1994), (reprint) · Zbl 0888.65010 |
| [45] | Schaeffer, G., Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees, Electron. J. Combin., 4, 1 (1997), Research Paper 20, 14 pp. (electronic) · Zbl 0885.05076 |
| [46] | Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101 |
| [47] | Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 64-74 (1968) · Zbl 0157.31101 |
| [48] | Tutte, W. T., Dichromatic sums for rooted planar maps, Proc. Sympos. Pure Math., 19, 235-245 (1971) · Zbl 0227.05103 |
| [49] | Tutte, W. T., Chromatic sums for rooted planar triangulations. II. The case \(\lambda = \tau + 1\), Canad. J. Math., 25, 657-671 (1973) · Zbl 0268.05112 |
| [50] | Tutte, W. T., Chromatic sums for rooted planar triangulations. III. The case \(\lambda = 3\), Canad. J. Math., 25, 780-790 (1973) · Zbl 0268.05113 |
| [51] | Tutte, W. T., Chromatic sums for rooted planar triangulations. IV. The case \(\lambda = \infty \), Canad. J. Math., 25, 929-940 (1973) · Zbl 0268.05114 |
| [52] | Tutte, W. T., Chromatic sums for rooted planar triangulations: the cases \(\lambda = 1\) and \(\lambda = 2\), Canad. J. Math., 25, 426-447 (1973) · Zbl 0253.05122 |
| [53] | Tutte, W. T., Chromatic sums for rooted planar triangulations. V. Special equations, Canad. J. Math., 26, 893-907 (1974) · Zbl 0287.05103 |
| [54] | Tutte, W. T., On a pair of functional equations of combinatorial interest, Aequationes Math., 17, 2-3, 121-140 (1978) · Zbl 0377.05025 |
| [55] | Tutte, W. T., Chromatic solutions, Canad. J. Math., 34, 3, 741-758 (1982) · Zbl 0458.05010 |
| [56] | Tutte, W. T., Chromatic solutions. II, Canad. J. Math., 34, 4, 952-960 (1982) · Zbl 0505.05030 |
| [57] | Tutte, W. T., Map-colourings and differential equations, (Progress in Graph Theory. Progress in Graph Theory, Waterloo, ON, 1982 (1984), Academic Press: Academic Press Toronto, ON), 477-485 · Zbl 0554.05029 |
| [58] | Tutte, W. T., Chromatic sums revisited, Aequationes Math., 50, 1-2, 95-134 (1995) · Zbl 0842.05031 |
| [59] | Walker, R. J., Algebraic Curves (1978), Springer-Verlag: Springer-Verlag New York, reprint of the 1950 edition · Zbl 0399.14016 |
| [60] | Welsh, D. J.A.; Merino, C., The Potts model and the Tutte polynomial, J. Math. Phys., 41, 3, 1127-1152 (2000) · Zbl 1045.82501 |
| [61] | Zinn-Justin, P., The dilute Potts model on random surfaces, J. Stat. Phys., 98, 1-2, j10-264 (2000) · Zbl 0957.82009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
