Mireille Bousquet-Mélou (CNRS, Université de Bordeaux)

Bousquet-Melou

Séjour: 1 au 5 octobre 2018 au cours duquel Mireille Bousquet-Mélou (CNRS, Université de Bordeaux) donnera une série de conférences dans le cadre de la chaire Aisenstadt 2018.

(Photo: Ivonne Vetter)

Counting lattice walks confined to cones

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.

This series of talks given in the framework of the Aisenstadt chair, will begin with a survey of this topic. The following two talks will deal respectively with proofs of algebraicicty (and D-algebraicity), and with recent progresses on walks with arbitrary steps.

 

DATES

Lundi 1er octobre 16h00

Mardi 2 octobre 16h00

Mercredi 3 octobre 16h00

 

LIEU

Centre de recherches mathématiques
Pavillon André-Aisenstadt, Université de Montréal
Salle 6254

Une réception suivra la conférence du lundi 1er octobre, au salon Maurice L'Abbé, Pavillon André-Aisenstadt (salle 6245).