Algebraic Graph Theory Seminar - Josip Smolcic

Title: Algorithms for Analytic Combinatorics in Several Variables

Abstract: In this presentation we will see how to apply the theory of complex analysis to study multivariate generating series by looking at several examples. Specifically, given a rational bivariate generating function G(x, y)/H(x, y) with coefficients f_{i, j} the objective is algorithmically determine asymptotic formulas to approximate f_{rn, sn} as n goes to infinity, for fixed positive integers r and s. In this presentation we demonstrate two approaches for determining the asymptotic formulae, each of which involve determining so-called minimal critical points of the denominator H(x, y) in the direction (r, s). The first approach uses numerical methods to solve systems of polynomial equations which depend on the given bivariate generating function to determine minimal points of the denominator, while the second involves analyzing a map h from the zero-set of H to the real numbers, known as a height map. Software developed for both of these purposes will be demonstrated.