×

Polynomial equations with one catalytic variable, algebraic series and map enumeration. (English) Zbl 1099.05043

From the authors’ abstract: Let \(F(t,u) \equiv F(u)\) be a formal power series in \(t\) with polynomial coefficients in \(u\). Let \(F_1,\dots,F_k\) be \(k\) formal power series in \(t\), independent of \(u\). Assume that all these series are characterized by a polynomial equation \(P(F(u),F_1,\dots,F_k,t,u)= 0.\) We prove that, under a mild hypothesis on the form of this equation, these \(k+1\) series are algebraic, and we give a strategy to compute a polynomial equation for each of them. This strategy generalizes the so-called kernel method and quadratic method, which apply, respectively, to equations that are linear and quadratic in \(F(u)\). Applications include the solution of numerous map enumeration problems, among which is the hard-particle model on general planar graphs.

MSC:

05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
05A15 Exact enumeration problems, generating functions

Software:

ROTA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci., 281, 1-2, 37-80 (2002) · Zbl 0996.68126
[2] 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
[3] M. Bardet, J.-C. Faugère, B. Salvy, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, in: International Conference on Polynomial System Solving, Proceedings of a conference held in Paris, France, in honor of Daniel Lazard, November 2004, pp. 71-74; M. Bardet, J.-C. Faugère, B. Salvy, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, in: International Conference on Polynomial System Solving, Proceedings of a conference held in Paris, France, in honor of Daniel Lazard, November 2004, pp. 71-74
[4] Basu, S.; Pollack, R.; Roy, M.-F., Algorithms in Real Algebraic Geometry, Algorithms Comput. Math., vol. 10 (2003), Springer-Verlag: Springer-Verlag Berlin
[5] 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
[6] O. Bernardi, On triangulations with high vertex degree, in: Formal Power Series and Algebraic Combinatorics, Taormina, Italy, 2005; O. Bernardi, On triangulations with high vertex degree, in: Formal Power Series and Algebraic Combinatorics, Taormina, Italy, 2005
[7] M. Bousquet-Mélou, Habilitation à diriger les recherches, Report 1154-96, LaBRI, Université Bordeaux 1, 1996; M. Bousquet-Mélou, Habilitation à diriger les recherches, Report 1154-96, LaBRI, Université Bordeaux 1, 1996
[8] Bousquet-Mélou, M., A method for the enumeration of various classes of column-convex polygons, Discrete Math., 154, 1-3, 1-25 (1996) · Zbl 0858.05006
[9] Bousquet-Mélou, M., Multi-statistic enumeration of two-stack sortable permutations, Electron. J. Combin., 5, 1 (1998), Research Paper 21, 12 p · Zbl 0890.05004
[10] Bousquet-Mélou, M., Counting walks in the quarter plane, (Mathematics and Computer Science 2. Mathematics and Computer Science 2, Versailles, 2002. Mathematics and Computer Science 2. Mathematics and Computer Science 2, Versailles, 2002, Trends Math. (2002), Birkhäuser: Birkhäuser Basel), 49-67 · Zbl 1026.05004
[11] 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
[12] Bousquet-Mélou, M.; Schaeffer, G., Enumeration of planar constellations, Adv. Appl. Math., 24, 4, 337-368 (2000) · Zbl 0955.05004
[13] Bousquet-Mélou, M.; Schaeffer, G., The degree distribution of bipartite planar maps: Applications to the Ising model
[14] Bouttier, J.; Di Francesco, P.; Guitter, E., Census of planar maps: From the one-matrix model solution to a combinatorial proof, Nucl. Phys. B, 645, 3, 477-499 (2002) · Zbl 0999.05052
[15] Bouttier, J.; Di Francesco, P.; Guitter, E., Critical and tricritical hard objects on bicolourable random lattices: Exact solutions, J. Phys. A, 35, 17, 3821-3854 (2002) · Zbl 1053.82018
[16] Bouttier, J.; Di Francesco, P.; Guitter, E., Combinatorics of hard particles on planar graphs, Nucl. Phys. B, 655, 3, 313-341 (2003) · Zbl 1009.82005
[17] Bouttier, J.; Di Francesco, P.; Guitter, E., Combinatorics of bicubic maps with hard particles · Zbl 1064.82020
[18] Brown, W. G., Enumeration of non-separable planar maps, Canad. J. Math., 15, 526-545 (1963) · Zbl 0115.40901
[19] Brown, W. G., Enumeration of triangulations of the disk, Proc. London Math. Soc. (3), 14, 746-768 (1964) · Zbl 0134.19503
[20] Brown, W. G., Enumeration of quadrangular dissections of the disk, Canad. J. Math., 17, 302-317 (1965) · Zbl 0138.19104
[21] Brown, W. G., On the existence of square roots in certain rings of power series, Math. Ann., 158, 82-89 (1965) · Zbl 0136.02503
[22] Brown, W. G., An algebraic technique for solving certain problems in the theory of graphs, (Theory of Graphs. Theory of Graphs, Proc. Colloq. held at Tihany, Hungary, September 1966 (1968), Academic Press) · Zbl 0155.31802
[23] Brown, W. G.; Tutte, W. T., On the enumeration of rooted non-separable planar maps, Canad. J. Math., 16, 572-577 (1964) · Zbl 0119.38804
[24] Cori, R.; Richard, J., Énumération des graphes planaires à l’aide des séries formelles en variables non commutatives, Discrete Math., 2, 115-162 (1972) · Zbl 0247.05140
[25] Cori, R.; Vauquelin, B., Planar maps are well labeled trees, Canad. J. Math., 33, 5, 1023-1042 (1981) · Zbl 0415.05020
[26] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergrad. Texts Math. (1997), Springer-Verlag: Springer-Verlag New York
[27] de Mier, A.; Noy, M., A solution to the tennis ball problem, Theoret. Comput. Sci., 346, 2-3, 254-264 (2005) · Zbl 1078.05006
[28] Fayolle, G.; Iasnogorodski, R., Two coupled processors: The reduction to a Riemann-Hilbert problem, Z. Wahrsch. Verw. Gebiete, 47, 3, 325-351 (1979) · Zbl 0395.68032
[29] Feretić, S., A new way of counting the column-convex polyominoes by perimeter, Discrete Math., 180, 1-3, 173-184 (1998) · Zbl 0894.05010
[30] S. Feretić, D. Svrtan, On the number of column-convex polyominoes with given perimeter and number of columns, in: Barlotti, Delest, Pinzani (Eds.), Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, Italy, 1993, pp. 201-214; S. Feretić, D. Svrtan, On the number of column-convex polyominoes with given perimeter and number of columns, in: Barlotti, Delest, Pinzani (Eds.), Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, Italy, 1993, pp. 201-214
[31] R. Flajolet, R. Sedgewick, Analytic combinatorics: Functional equations, rational, and algebraic functions, Technical Report RR4103, INRIA, 2001, a component of the book project “Analytic Combinatorics,” available at http://www.inria.fr/rrrt/rr-4103.html; R. Flajolet, R. Sedgewick, Analytic combinatorics: Functional equations, rational, and algebraic functions, Technical Report RR4103, INRIA, 2001, a component of the book project “Analytic Combinatorics,” available at http://www.inria.fr/rrrt/rr-4103.html
[32] Gao, Z. J.; Wanless, I. M.; Wormald, N. C., Counting 5-connected planar triangulations, J. Graph Theory, 38, 1, 18-35 (2001) · Zbl 0983.05052
[33] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration, Wiley-Interscience Ser. Discrete Math. (1983), John Wiley & Sons: John Wiley & Sons New York · Zbl 0519.05001
[34] Knuth, D. E., The Art of Computer Programming, vol. 1: Fundamental Algorithms (1968), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[35] Lang, S., Algebra (1965), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0193.34701
[36] McCallum, S., Factors of iterated resultants and discriminants, J. Symbolic Comput., 27, 4, 367-385 (1999) · Zbl 0927.12005
[37] Prodinger, H., The kernel method: A collection of examples, Sém. Lothar. Combin., 50 (2003/04), Art. B50f, 19 p. (electronic) · Zbl 1063.05011
[38] 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 p. (electronic) · Zbl 0885.05076
[39] G. Schaeffer, personal communication, 2002; G. Schaeffer, personal communication, 2002
[40] Simion, R., Noncrossing partitions, Discrete Math., 217, 1-3, 367-409 (2000) · Zbl 0959.05009
[41] Stanley, R. P., Enumerative Combinatorics, vol. 2, Cambridge Stud. Adv. Math., vol. 62 (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0928.05001
[42] Temperley, H. N.V., Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, Phys. Rev. (2), 103, 1-16 (1956) · Zbl 0075.20502
[43] Tutte, W. T., A census of planar triangulations, Canad. J. Math., 14, 21-38 (1962) · Zbl 0103.39603
[44] Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 64-74 (1968) · Zbl 0157.31101
[45] Tutte, W. T., Chromatic sums for rooted planar triangulations. V. Special equations, Canad. J. Math., 26, 893-907 (1974) · Zbl 0287.05103
[46] Tutte, W. T., Chromatic sums revisited, Aequationes Math., 50, 1-2, 95-134 (1995) · Zbl 0842.05031
[47] Walker, R. J., Algebraic Curves (1978), Springer-Verlag: Springer-Verlag New York, Reprint of the 1950 edition
[48] D. Xu, Generalizations of two-stack-sortable permutations, PhD thesis, Brandeis University, Waltham, MA, 2002; D. Xu, Generalizations of two-stack-sortable permutations, PhD thesis, Brandeis University, Waltham, MA, 2002
[49] Zeilberger, D., A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3 n)! /((n + 1)!(2 n + 1)!)\), Discrete Math., 102, 1, 85-93 (1992) · Zbl 0754.05006
[50] Zeilberger, D., The umbral transfer-matrix method: I. Foundations, J. Combin. Theory Ser. A, 91, 451-463 (2000) · Zbl 0961.05003
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.