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