Automatic classification of lattice walks in three dimensions

Lattice walks are a classical topic in combinatorics. The principal question is: how many possibilities are there to go from some prescribed startpoint in some prescribed grid with some prescribed number of steps to some prescribed endpoint. For example, on a chess board, on how many different paths can the king move from A1 to H8 in n moves, where n is a variable. The answer is a certain sequence of numbers and it may be of interest to find a closed form, or a recurrence, or an asymptotic form of this sequence, or at least some of its algebraic properties. In many cases, such questions can be answered quickly by computer algebra. The use of computer algebra makes it feasible to consider an enormous number of different walk types and to search systematically for "interesting" cases. For a particular class of walks in three dimensions, a systematic classification has been initiated in [BoKa09]. The goal of a Masters thesis could be to continue this work. The thesis would be co-advised by Alin Bostan from INRIA Paris-Rocquencourt and Manuel Kauers from RISC in Linz.

[BoKa09] Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks. Proceedings FPSAC'09, Discrete Mathematics and Theoretical Computer Science, pp. 203–217, 2009.