Counting coloured planar maps: differential equations. (English) Zbl 1367.05045
Summary: We address the enumeration of \(q\)-coloured planar maps counted by the number of edges and the number of monochromatic edges. We prove that the associated generating function is differentially algebraic, that is, satisfies a non-trivial polynomial differential equation with respect to the edge variable. We give explicitly a differential system that characterizes this series. We then prove a similar result for planar triangulations, thus generalizing a result of Tutte dealing with their proper \(q\)-colourings. In statistical physics terms, we solve the \(q\)-state Potts model on random planar lattices. This work follows a first paper by the same authors, where the generating function was proved to be algebraic for certain values of \(q\), including \(q=1, 2\) and 3. It is known to be transcendental in general. In contrast, our differential system holds for an indeterminate \(q\). For certain special cases of combinatorial interest (four colours; proper \(q\)-colourings; maps equipped with a spanning forest), we derive from this system, in the case of triangulations, an explicit differential equation of order 2 defining the generating function. For general planar maps, we also obtain a differential equation of order 3 for the four-colour case and for the self-dual Potts model.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C30 | Enumeration in graph theory |
| 05A15 | Exact enumeration problems, generating functions |
Keywords:
enumeration of \(q\)-coloured planar maps; \(q\)-state Potts model on random planar latticesSoftware:
ROTAReferences:
| [1] | Beffara V., Duminil-Copin H.: The self-dual point of the two-dimensional random-cluster model is critical for \[{q\geq 1}\] q≥1. Probab. Theory Relat. Fields 153(3-4), 511-542 (2012) · Zbl 1257.82014 · doi:10.1007/s00440-011-0353-8 |
| [2] | Bernardi O., Bousquet-Mélou M.: Counting colored planar maps: algebraicity results. J. Combin. Theory Ser. B 101(5), 315-377 (2011) arXiv:0909.1695 · Zbl 1223.05123 · doi:10.1016/j.jctb.2011.02.003 |
| [3] | Bessis D., Itzykson C., Zuber J.B.: Quantum field theory techniques in graphical enumeration. Adv. Appl. Math. 1(2), 109-157 (1980) · Zbl 0453.05035 · doi:10.1016/0196-8858(80)90008-1 |
| [4] | Bollobás B.: Modern Graph Theory, Vol 184 of Graduate Texts in Mathematics. Springer, New York (1998) · Zbl 0902.05016 |
| [5] | Bonichon, N., Bousquet-Mélou, M., Fusy, É.: Baxter permutations and plane bipolar orientations. Sém. Lothar. Combin., 61A:Art. B61Ah, 29, 2009/11 · Zbl 1205.05004 |
| [6] | Borot G., Bouttier J., Guitter E.: Loop models on random maps via nested loops: case of domain symmetry breaking and application to the Potts model. J. Phys. A 45, 494017 (2012) · Zbl 1257.82016 · doi:10.1088/1751-8113/45/49/494017 |
| [7] | Bostan A., Raschel K., Salvy B.: Non-D-finite excursions in the quarter plane. J. Combin. Theory Ser. A 121, 45-63 (2014) · Zbl 1279.05003 · doi:10.1016/j.jcta.2013.09.005 |
| [8] | 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) · doi:10.1016/0370-2693(87)90312-1 |
| [9] | Bousquet-Mélou, M.: Counting planar maps, coloured or uncoloured. In: Surveys in Combinatorics 2011, volume 392 of London Math. Soc. Lecture Note Ser., pp. 1-49. Cambridge Univ. Press, Cambridge (2011) · Zbl 1244.05118 |
| [10] | Bousquet-Mélou M., Courtiel J.: Spanning forests in regular planar maps. J. Combin. Theory Ser. A 135, 1-59 (2015) arXiv:1306.4536 · Zbl 1319.05070 · doi:10.1016/j.jcta.2015.04.002 |
| [11] | Bousquet-Mélou M., Jehanne A.: Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Combin. Theory Ser. B 96, 623-672 (2006) · Zbl 1099.05043 · doi:10.1016/j.jctb.2005.12.003 |
| [12] | Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane. In: Algorithmic Probability and Combinatorics, volume 520 of Contemp. Math., pp. 1-39. Amer. Math. Soc., Providence (2010) · Zbl 1209.05008 |
| [13] | Bousquet-Mélou, M., Schaeffer, G.: The degree distribution of bipartite planar maps: applications to the Ising model. In: Eriksson, K., Linusson, S. (eds.) Formal Power Series and Algebraic Combinatorics, pp. 312-323, Vadstena, Sweden, 2003. Long version on arXiv:math/0211070 · Zbl 0287.05103 |
| [14] | Bouttier, J., Di Francesco, P., Guitter, E.: Planar maps as labeled mobiles. Electron. J. Combin., 11(1):Research Paper 69 (electronic) (2004) · Zbl 1060.05045 |
| [15] | Bouttier J., Francesco P., Guitter E.: Blocked edges on Eulerian maps and mobiles: application to spanning trees, hard particles and the Ising model. J. Phys. A 40(27), 7411-7440 (2007) · Zbl 1147.82003 · doi:10.1088/1751-8113/40/27/002 |
| [16] | Brézin E., Itzykson C., Parisi G., Zuber J. B.: Planar diagrams. Comm. Math. Phys. 59(1), 35-51 (1978) · Zbl 0997.81548 · doi:10.1007/BF01614153 |
| [17] | Brown W.G.: On the existence of square roots in certain rings of power series. Math. Ann. 158, 82-89 (1965) · Zbl 0136.02503 · doi:10.1007/BF01370732 |
| [18] | Castelli Aleardi, L., Devillers, O., Schaeffer, G.: Optimal succinct representations of planar maps. In: Computational Geometry (SCG’06), pp. 309-318. ACM, New York (2006) · Zbl 1153.68515 |
| [19] | Chen, L.: Basic properties of the infinite critical FK random map. arXiv:1502.01013 · Zbl 1381.60033 |
| [20] | Denef J., Lipshitz L.: Power series solutions of algebraic differential equations. Math. Ann. 267(2), 213-238 (1984) · Zbl 0518.12015 · doi:10.1007/BF01579200 |
| [21] | Francesco P., Ginsparg P., Zinn-Justin J.: 2D gravity and random matrices. Phys. Rep. 254(1-2), 133 (1995) · doi:10.1016/0370-1573(94)00084-G |
| [22] | Duplantier B., Kostov I.: Conformal spectra of polymers on a random surface. Phys. Rev. Lett. 61(13), 1433-1437 (1988) · doi:10.1103/PhysRevLett.61.1433 |
| [23] | 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 · doi:10.1016/S0370-2693(99)00925-9 |
| [24] | Flajolet P., Sedgewick R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001 · doi:10.1017/CBO9780511801655 |
| [25] | Fortuin C. M., Kasteleyn P. W.: On the random cluster model: I. Introduction and relation to other models. Physica 57, 536-564 (1972) · doi:10.1016/0031-8914(72)90045-6 |
| [26] | Giménez O., Noy M.: Asymptotic enumeration and limit laws of planar graphs. J. Am. Math. Soc 22(2), 309-329 (2009) · Zbl 1206.05019 · doi:10.1090/S0894-0347-08-00624-3 |
| [27] | Goulden, I. P., Jackson, D. M.: Combinatorial enumeration. Wiley, New York (1983). Wiley-Interscience Series in Discrete Mathematics · Zbl 0519.05001 |
| [28] | Goulden I. P., Jackson D. M.: The KP hierarchy, branched covers, and triangulations. Adv. Math. 219(3), 932-951 (2008) · Zbl 1158.37026 · doi:10.1016/j.aim.2008.06.013 |
| [29] | Guionnet A., Jones V. F. R., Shlyakhtenko D., Zinn-Justin P.: Loop models, random matrices and planar algebras. Comm. Math. Phys. 316(1), 45-97 (2012) · Zbl 1277.82013 · doi:10.1007/s00220-012-1573-1 |
| [30] | Jackson D. M.: Counting cycles in permutations by group characters, with application to a topological problem. Trans. Am. Math. Soc. 299(2), 785-801 (1987) · Zbl 0655.05005 · doi:10.1090/S0002-9947-1987-0869231-9 |
| [31] | Jackson D. M., Visentin T. I.: A character-theoretic approach to embeddings of rooted maps in an orientable surface of given genus. Trans. Am. Math. Soc. 322(1), 343-363 (1990) · Zbl 0747.05008 |
| [32] | Kazakov V. A.: Ising model on a dynamical planar random lattice: exact solution. Phys. Lett. A 119(3), 140-144 (1986) · doi:10.1016/0375-9601(86)90433-0 |
| [33] | Kurkova I., Raschel K.: On the functions counting walks with small steps in the quarter plane. Publ. Math. Inst. Hautes études Sci. 116, 69-114 (2012) · Zbl 1255.05012 · doi:10.1007/s10240-012-0045-7 |
| [34] | Mullin R. C.: On the enumeration of tree-rooted maps. Can. J. Math. 19, 174-183 (1967) · Zbl 0148.17705 · doi:10.4153/CJM-1967-010-x |
| [35] | Odlyzko, A. M., Richmond, L. B.: A differential equation arising in chromatic sum theory. In: Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Raton, 1983), volume 40, pp. 263-275 (1983) · Zbl 0535.05035 |
| [36] | Schaeffer, G.: Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. Electron. J. Combin., 4(1):Research Paper 20 (electronic) (1997) · Zbl 0885.05076 |
| [37] | Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 90), pp. 138-148, San Francisco, CA (1990) · Zbl 0786.05029 |
| [38] | Sheffield S.: Quantum gravity and inventory accumulation. Ann. PNBA B 44(6), 3804-3848 (2016) arXiv:1108.2241 · Zbl 1359.60120 |
| [39] | Stanley R. P.: Enumerative Combinatorics 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1999) · Zbl 0928.05001 · doi:10.1017/CBO9780511609589 |
| [40] | Tutte W. T.: On the enumeration of planar maps. Bull. Am. Math. Soc 74, 64-74 (1968) · Zbl 0157.31101 · doi:10.1090/S0002-9904-1968-11877-4 |
| [41] | Tutte W. T.: On the enumeration of four-colored maps. SIAM J. Appl. Math. 17, 454-460 (1969) · Zbl 0176.22401 · doi:10.1137/0117044 |
| [42] | Tutte W. T.: Chromatic sums for rooted planar triangulations. II. The case \[{\lambda =\tau +1}\] λ=τ+1. Can. J. Math 25, 657-671 (1973) · Zbl 0268.05112 · doi:10.4153/CJM-1973-066-8 |
| [43] | Tutte W. T.: Chromatic sums for rooted planar triangulations. III. The case \[{\lambda =3}\] λ=3. Can. J. Math. 25, 780-790 (1973) · Zbl 0268.05113 · doi:10.4153/CJM-1973-080-7 |
| [44] | Tutte W. T.: Chromatic sums for rooted planar triangulations. IV. The case \[{\lambda =\infty }\] λ=∞. Can. J. Math. 25, 929-940 (1973) · Zbl 0268.05114 · doi:10.4153/CJM-1973-099-9 |
| [45] | Tutte W.T.: Chromatic sums for rooted planar triangulations: the cases \[{\lambda =1}\] λ=1 and \[{\lambda =2}\] λ=2. Can. J. Math. 25, 426-447 (1973) · Zbl 0253.05122 · doi:10.4153/CJM-1973-043-3 |
| [46] | Tutte W. T.: Chromatic sums for rooted planar triangulations. V. Special equations. Can. J. Math. 26, 893-907 (1974) · Zbl 0287.05103 · doi:10.4153/CJM-1974-084-1 |
| [47] | Tutte W. T.: On a pair of functional equations of combinatorial interest. Aequ. Math. 17(2-3), 121-140 (1978) · Zbl 0377.05025 · doi:10.1007/BF01818554 |
| [48] | Tutte W. T.: Chromatic solutions. Can. J. Math. 34(3), 741-758 (1982) · Zbl 0458.05010 · doi:10.4153/CJM-1982-051-4 |
| [49] | Tutte W. T.: Chromatic solutions. II. Can. J. Math. 34(4), 952-960 (1982) · Zbl 0505.05030 · doi:10.4153/CJM-1982-068-1 |
| [50] | Tutte, W. T.: Map-colourings and differential equations. In: Progress in Graph Theory (Waterloo, ON, 1982), pp. 477-485. Academic Press, Toronto (1984) · Zbl 0554.05029 |
| [51] | Tutte W. T.: Chromatic sums revisited. Aequ. Math. 50(1-2), 95-134 (1995) · Zbl 0842.05031 · doi:10.1007/BF01831115 |
| [52] | Welsh D.J.A., Merino C.: The Potts model and the Tutte polynomial. J. Math. Phys. 41(3), 1127-1152 (2000) · Zbl 1045.82501 · doi:10.1063/1.533181 |
| [53] | Wu F. Y.: The Potts model. Rev. Mod. Phys. 54(1), 235-268 (1982) · doi:10.1103/RevModPhys.54.235 |
| [54] | Zeilberger D.: The umbral transfer-matrix method: I. Foundations. J. Comb. Theory, Ser. A 91, 451-463 (2000) · Zbl 0961.05003 · doi:10.1006/jcta.2000.3110 |
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.
