Classifying walks in the quarter plane
Marni Mishna (Fields Institute)
The objects of study here are two-dimensional lattice walks, with a fixed
set of step directions, restricted to the first quadrant. These walks are
well studied, both in a general context of probabilistic models, and
specifically as particular case studies for fixed direction sets, notably
the so-called Kreweras' walks defined by the direction set {NE, W, S}.
The goal here is to examine two series associated to these walks: a simple
length generating function, and a complete generating function which
encodes endpoints of walks, and to determine combinatorial criteria which
decide when these series are algebraic, D-finite, or none of the above.
(Indeed we have examples that we believe to be non-D-finite)
We shall present an (almost) complete classification of all nearest
neighbour walks where the set of directions is of cardinality three, and
discuss how this leads to a natural, well supported, conjecture for the
classification of nearest walks with any direction set.
(Work in progress with M. Bousquet-Melou)
Applied Algebra seminar home