An elementary solution of Gessel's walks in the quadrant
From MaRDI portal
Publication:323719
DOI10.1016/J.AIM.2016.08.038zbMATH Open1351.05017arXiv1503.08573OpenAlexW2963852056MaRDI QIDQ323719FDOQ323719
Authors: Mireille Bousquet-Mélou 
Publication date: 10 October 2016
Published in: Advances in Mathematics (Search for Journal in Brave)
Abstract: Around 2000, Ira Gessel conjectured that the number of lattice walks in the quadrant N^2, starting and ending at the origin (0,0) and taking their steps in {E,NE,W,SW} had a simple hypergeometric form. In the following decade, this problem was recast in the systematic study of walks with small steps (that is,steps in {-1,0,1}^2) confined to the quadrant. The generating functions of such walks are archetypal solutions of partial discrete differential equations.A complete classification of quadrant walks according to the nature of their generating function(algebraic, D-finite or not) is now available, but Gessel'swalks remained mysterious because they were the only model among the 23D-finite ones that had not been given an elementarysolution. Instead, Gessel's conjecture was first proved usingan inventive computer algebra approach in 2008. A year later, the associated three-variate generating function was proved to be algebraic by a computer algebra tour de force. This was re-proved recently using elaborate complex analysis machinery. We give here an elementary and constructive proof. Our approach also solves other quadrant models (with multiple steps) recently proved to be algebraic via computer algebra.
Full work available at URL: https://arxiv.org/abs/1503.08573
Recommendations
Exact enumeration problems, generating functions (05A15) Combinatorial aspects of representation theory (05E10)
Cites Work
- The On-Line Encyclopedia of Integer Sequences
- Proof of the alternating sign matrix conjecture
- Title not available (Why is that?)
- Walks in the quarter plane with multiple steps
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classifying lattice walks restricted to the quarter plane
- Generating functions for generating trees
- Linear recurrences with constant coefficients: The multivariate case
- Basic analytic combinatorics of directed lattice paths
- Walks confined in a quadrant are not always D-finite
- On the functions counting walks with small steps in the quarter plane
- About a possible analytic approach for walks in the quarter plane with arbitrary big jumps
- Walks with small steps in the quarter plane
- On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane
- Singularity Analysis Via the Iterated Kernel Method
- Non-D-finite excursions in the quarter plane
- Counting Walks in the Quarter Plane
- The complete generating function for Gessel walks is algebraic
- On 3-dimensional lattice walks confined to the positive octant
- Walks in the quarter plane: Kreweras' algebraic model
- Explicit expression for the generating function counting Gessel's walks
- Two non-holonomic lattice walks in the quarter plane
- Two Parallel Queues Created by Arrivals with Two Demands I
- Die Approximationseigenschaft lokaler Ringe
- A human proof of Gessel's lattice path conjecture
- Counting walks in a quadrant: a unified approach via boundary value problems
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- The Number of Degree-Restricted Rooted Maps on the Sphere
- Exit times from cones in \({\mathbb{R}}^ n\) of Brownian motion
- A probabilistic method for lattice path enumeration
- Proof of two conjectures of Petkovšek and Wilf on Gessel walks
- Counting colored planar maps: algebraicity results
- Random walks in cones: the case of nonzero drift
- On the existence of square roots in certain rings of power series
- Proof of Ira Gessel's lattice path conjecture
- Counting planar maps, coloured or uncoloured
- A Census of Planar Triangulations
- The quasi-holonomic ansatz and restricted lattice walks
- Towards a human proof of Gessel's conjecture
- General Néron desingularization and approximation
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- On the Enumeration of Rooted Non-Separable Planar Maps
- On the exit time from a cone for Brownian motion with drift
Cited In (26)
- Winding of simple walks on the square lattice
- On walks avoiding a quadrant
- Proof of Ira Gessel's lattice path conjecture
- The complete generating function for Gessel walks is algebraic
- Counting quadrant walks via Tutte's invariant method
- Asymptotic lattice path enumeration using diagonals
- Towards a human proof of Gessel's conjecture
- Walks in the quarter plane: Kreweras' algebraic model
- The research and progress of the enumeration of lattice paths
- Explicit expression for the generating function counting Gessel's walks
- Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior
- Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
- Square lattice walks avoiding a quadrant
- The Gram-Schmidt walk: a cure for the Banaszczyk blues
- Encoding algebraic power series
- Algebraic solutions of linear differential equations: an arithmetic approach
- A decomposition of ballot permutations, pattern avoidance and Gessel walks
- Enumeration of walks with small steps avoiding a quadrant
- Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity
- Walks obeying two-step rules on the square lattice: full, half and quarter planes
- Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
- Proof of two conjectures of Petkovšek and Wilf on Gessel walks
- A mating-of-trees approach for graph distances in random planar maps
- Counting walks with large steps in an orthant
- Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
- Title not available (Why is that?)
Uses Software
This page was built for publication: An elementary solution of Gessel's walks in the quadrant
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q323719)
