Mireille Bousquet-Melou (CNRS & Université de Bordeaux)

Counting lattice walks confined to cones

vendredi 8 novembre 2019, 11h00 - 12h00

Salle du conseil, espace Turing


The study of lattice walks confined to cones is a very lively topic in combinatorics and in probability theory, which has witnessed rich developments in the past 20 years. In a typical problem, one is given a finite set of allowed steps S in Z^d, and a cone C in R^d. Clearly, there are |S|^n walks of length n that start from the origin and take their steps in S. But how many of them remain the the cone C? One of the motivations for studying such questions is that lattice walks are ubiquitous in various mathematical fields, where they encode important classes of objects: in discrete mathematics (permutations, trees, words…), in statistical physics (polymers…), in probability theory (urns, branching processes, systems of queues), among other fields. The systematic study of these counting problems started about 20 years ago. Beforehand, only sporadic cases had been solved, with the exception of walks with small steps confined to a Weyl chamber, for which a general reflection principle had been developed. Since then, several approaches have been combined to understand how the choice of the steps and of the cone influence the nature of the counting sequence a(n), or of the the associated series A(t)=\sum a(n) t^n. For instance, if C is the first quadrant of the plane and S only consists of « small » steps, it is now understood when A(t) is rational, algebraic, or when it satisfies a linear, or a non-linear, differential equation. Even in this simple case, the classification involves tools coming from an attractive variety of fields: algebra on formal power series, complex analysis, computer algebra, differential Galois theory, to cite just a few. And much remains to be done, for other cones and sets of steps.