Counting quadrant walks via Tutte's invariant method (extended abstract)
From MaRDI portal
Publication:5111046
zbMATH Open1440.05019arXiv1511.04298MaRDI QIDQ5111046FDOQ5111046
Olivier Bernardi, Mireille Bousquet-Mélou, Kilian Raschel
Publication date: 26 May 2020
Abstract: 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, 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).
Full work available at URL: https://arxiv.org/abs/1511.04298
Exact enumeration problems, generating functions (05A15) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)
Cites Work
- Title not available (Why is that?)
- Walks in the quarter plane with multiple steps
- Title not available (Why is that?)
- On the functions counting walks with small steps in the quarter plane
- Random walks in cones
- Walks with small steps in the quarter plane
- Counting Walks in the Quarter Plane
- The complete generating function for Gessel walks is algebraic
- Two non-holonomic lattice walks in the quarter plane
- A human proof of Gessel's lattice path conjecture
- Random Walk in a Weyl Chamber
- Title not available (Why is that?)
- Counting walks in a quadrant: a unified approach via boundary value problems
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- A probabilistic method for lattice path enumeration
- Proof of Ira Gessel's lattice path conjecture
- The quasi-holonomic ansatz and restricted lattice walks
- Chromatic sums revisited
Cited In (14)
- Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
- Green's functions with oblique Neumann boundary conditions in the quadrant
- Exact solution of some quarter plane walks with interacting boundaries
- Asymptotics of 3-stack-sortable permutations
- Walks with small steps in the 4D-orthant
- On the nature of four models of symmetric walks avoiding a quadrant
- Enumeration of walks with small steps avoiding a quadrant
- On the kernel curves associated with walks in the quarter plane
- Differential transcendence of Bell numbers and relatives: a Galois theoretic approach
- On differentially algebraic generating series for walks in the quarter plane
- Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
- Quadrant walks starting outside the quadrant
- Discrete harmonic functions in the three-quarter plane
- Counting walks with large steps in an orthant
Uses Software
This page was built for publication: Counting quadrant walks via Tutte's invariant method (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111046)
