Stephen Melczer ; Mark C. Wilson - Asymptotics of lattice walks via analytic combinatorics in several variables

dmtcs:6390 - Discrete Mathematics & Theoretical Computer Science, April 22, 2020, DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016) - https://doi.org/10.46298/dmtcs.6390
Asymptotics of lattice walks via analytic combinatorics in several variablesArticle

Authors: Stephen Melczer ORCID1,2; Mark C. Wilson 3

  • 1 Cheriton School of Computer Science [Waterloo]
  • 2 Arithmetic and Computing
  • 3 Department of Computer Science [Auckland]

We consider the enumeration of walks on the two-dimensional non-negative integer lattice with steps defined by a finite set S ⊆ {±1, 0}2 . Up to isomorphism there are 79 unique two-dimensional models to consider, and previous work in this area has used the kernel method, along with a rigorous computer algebra approach, to show that 23 of the 79 models admit D-finite generating functions. In 2009, Bostan and Kauers used Pade ́-Hermite approximants to guess differential equations which these 23 generating functions satisfy, in the process guessing asymptotics of their coefficient sequences. In this article we provide, for the first time, a complete rigorous verification of these guesses. Our technique is to use the kernel method to express 19 of the 23 generating functions as diagonals of tri-variate rational functions and apply the methods of analytic combinatorics in several variables (the remaining 4 models have algebraic generating functions and can thus be handled by univariate techniques). This approach also shows the link between combinatorial properties of the models and features of its asymptotics such as asymptotic and polynomial growth factors. In addition, we give expressions for the number of walks returning to the x-axis, the y-axis, and the origin, proving recently conjectured asymptotics of Bostan, Chyzak, van Hoeij, Kauers, and Pech.


Volume: DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)
Published on: April 22, 2020
Imported on: July 4, 2016
Keywords: Combinatorics,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

2 Documents citing this article

Consultation statistics

This page has been seen 168 times.
This article's PDF has been downloaded 254 times.