Proceedings of the 28-th International Conference on Formal Power Series and Algebraic Combinatorics
4-8 Jul 2016 Vancouver, British Columbia (Canada)
Counting quadrant walks via Tutte's invariant method
Olivier Bernardi  1  , Mireille Bousquet-Melou  2  , Kilian Raschel  3@  
1 : Department of Mathematics [Waltham]  -  Website
University of Brandeis Waltham MA 02454-9110 USA -  États-Unis
2 : Laboratoire Bordelais de Recherche en Informatique  (LaBRI)  -  Website
Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Centre National de la Recherche Scientifique : UMR5800
Domaine Universitaire 351, cours de la Libération 33405 Talence Cedex -  France
3 : Laboratoire de Mathématiques et Physique Théorique  (LMPT)  -  Website
Université de Tours, Centre national de la recherche scientifique - CNRS (France)
Avenue Monge Parc de Grandmont - 37200 Tours -  France

In the 1970s, Tutte developed a clever algebraic approach, based on certain “invariants”, to solve a func- tional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past decade to a rich col- lection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps.

We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic (with one small exception). This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity comes out (almost) automatically.

Then, we move to an analytic viewpoint which has already proved very powerful, leading in particular to integral expressions of the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions of the generating function, and a proof that this series is differentially algebraic (that is, satisfies a non-linear differential equation). This analytic approach solves as well the algebraic model left unsolved in the first part. 

  • Poster
Online user: 1