Lattice path asymptotics via analytic combinatorics

12/06/2016 - 12:15pm
12/06/2016 - 1:10pm
Mark C. Wilson (University of Auckland, New Zealand)

Lattice paths are a classical topic in combinatorics, with many applications. I report on joint work with Stephen Melczer (PhD student, Lyon/Waterloo). We consider the computation of $f_n(S)$, the number of $n$-step nearest-neighbor walks on the two dimensional non-negative integer lattice with a finite set $S$ of allowable steps. Up to isomorphism there are 79 models to consider, and previous work has shown that 23 of these satisfy a well-behaved recursion for $f_n(S)$. In 2009, Bostan and Kauers guessed asymptotics of $f_n(S)$ in these 23 cases. We provide, for the first time, a complete rigorous verification of these guesses. Our technique is to express 19 of the 23 GFs as diagonals of trivariate rational functions, and apply recently derived general methods of analytic combinatorics in several variables, as described in my 2013 book with Robin Pemantle. This approach also shows a direct link between combinatorial properties of the models and features of its asymptotics. In addition, we give using the same methodology 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. I will attempt to cover all required background and will present many examples. If time permits I will explain how similar but less comprehensive results can be obtained in arbitrary dimension.

Millikan 2099, Pomona College