×

zbMATH — the first resource for mathematics

Asymptotics of bivariate analytic functions with algebraic singularities. (English) Zbl 1369.05012
Summary: In this paper, we use the multivariate analytic techniques of R. Pemantle and M. C. Wilson [Analytic combinatorics in several variables. Cambridge Studies in Advanced Mathematics 140. Cambridge: Cambridge University Press (2013; Zbl 1297.05004)] to derive asymptotic formulae for the coefficients of a broad class of multivariate generating functions with algebraic singularities. Then, we apply these results to a generating function encoding information about the stationary distributions of a graph coloring algorithm studied by S. Butler et al. [Adv. Appl. Math. 69, 46–64 (2015; Zbl 1327.05306)]. Historically, P. Flajolet and A. M. Odlyzko [SIAM J. Discrete Math. 3, No. 2, 216–240 (1990; Zbl 0712.05004)] analyzed the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Z. Gao and L. B. Richmond [J. Comput. Appl. Math. 41, No. 1–2, 177–186 (1992; Zbl 0755.05004)] and H. K. Hwang [Ann. Appl. Probab. 6, No. 1, 297–319 (1996; Zbl 0863.60013)], in both cases by immediately reducing the multivariate case to the univariate case. Pemantle and Wilson [loc. cit.] outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions. These multivariate techniques are used here to analyze functions with algebraic singularities.

MSC:
05A15 Exact enumeration problems, generating functions
Software:
FGb; RAGlib
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bender, E. A.; Richmond, L. B., Central and local limit theorems applied to asymptotic enumeration. II. multivariate generating functions, J. Combin. Theory Ser. A, 34, 255-265, (1983) · Zbl 0511.05003
[2] Butler, S.; Chung, F.; Cummings, J.; Graham, R., Edge flipping in the complete graph, preprint, available online: · Zbl 1327.05306
[3] Faugère, J.-C., Fgb: a library for computing Gröbner bases, (Fukuda, Komei; Hoeven, Joris; Joswig, Michael; Takayama, Nobuki, Mathematical Software - ICMS 2010, Lecture Notes in Comput. Sci., vol. 6327, (September 2010), Springer Berlin, Heidelberg), 84-87, available online: · Zbl 1294.68156
[4] Flajolet, P.; Odlyzko, A. M., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 216-240, (1990), available online: · Zbl 0712.05004
[5] Gao, Z.; Richmond, L. B., Central and local limit theorems applied to asymptotic enumeration. IV. multivariate generating functions, J. Comput. Appl. Math., 41, 177-186, (1992) · Zbl 0755.05004
[6] Goresky, M.; MacPherson, R., Stratified Morse theory, (1988), Springer-Verlag Berlin, Heidelberg, available online: · Zbl 0639.14012
[7] Greenwood, T., Asymptotics of bivariate analytic functions with algebraic singularities, (DMTCS Proc., BC, (2016)), 599-610, available online:
[8] Hwang, H.-K., Large deviations for combinatorial distributions. I. central limit theorems, Ann. Appl. Probab., 6, 297-319, (1996), available online: · Zbl 0863.60013
[9] Hwang, H.-K., Large deviations for combinatorial distributions. II. local limit theorems, Ann. Appl. Probab., 8, 163-181, (1998), available online: · Zbl 0954.60020
[10] Pemantle, R.; Wilson, M., Analytic combinatorics in several variables, (2013), Cambridge University Press New York, available online: · Zbl 1297.05004
[11] Poznanović, S.; Heitsch, C. E., Asymptotic distribution of motifs in a stochastic context-free grammar model of RNA folding, J. Math. Biol., 1743-1772, (Dec 2014), available online:
[12] Raichev, A.; Wilson, M., Asymptotics of coefficients of multivariate generating functions: improvements for smooth points, Electron. J. Combin., 15, (2008), available online: · Zbl 1165.05309
[13] Safey El Din, M., Raglib, a Maple package dedicated to real solutions of polynomial systems, (March 2015), available online:
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.