Counting lattice walks confined to cones (première partie)
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.
Walks in the quadrant: Tutte's invariant method (deuxième partie)
The common starting point to all approaches in the (exact) enumeration of quadrant walks is a functional equation that defines a three variable power series, counting these walks according to their length and the coordinates of their endpoint. Similar equations appeared in the seventies in the work of William Tutte on the enumeration of properly coloured planar maps. In particular, Tutte devoted ten years (and as many papers) to the enumeration of properly coloured triangulations, for which he established, at the end, a non-linear differential equation for the main generating function.
In this talk, we will show how to apply (and then to extend to a more analytic framework) Tutte's ideas to treat in the uniform manner two kinds of quadrant problems:
- the 4 that have an algebraic generating function
- the 9 that have a differentially algebraic (but not differentially finite) generating function.
Tutte's notion of "invariants" is central to this solution.
These results have been obtained in collaboration with Olivier Bernardi and Kilian Raschel.
Gratuit
Mots clés
Disciplines