dmtcs:6416 
Discrete Mathematics & Theoretical Computer Science,
April 22, 2020,
DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)

https://doi.org/10.46298/dmtcs.6416
Counting quadrant walks via Tutte's invariant method (extended abstract)
2 Laboratoire Bordelais de Recherche en Informatique
3 Laboratoire de Mathématiques et Physique Théorique
In the 1970s, Tutte developed a clever algebraic approach, based on certain " invariants " , to solve a functional 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 collection of attractive results dealing with the nature (algebraic, Dfinite 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 nonDfinite cases, as well as to proofs of nonDfiniteness. 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 integralfree expressions of the generating function, and a proof that this series is differentially algebraic (that is, satisfies a nonlinear differential equation).
Franceschi, Sandro, 2020, Greenâs Functions With Oblique Neumann Boundary Conditions In The Quadrant, Journal Of Theoretical Probability, 34, 4, pp. 17751810, 10.1007/s10959020010438.
Franceschi, Sandro; Raschel, Kilian, 2017, Tutteâs Invariant Approach For Brownian Motion Reflected In The Quadrant, ESAIM: Probability And Statistics, 21, pp. 220234, 10.1051/ps/2017006.