Higher dimensional lattice walks: connecting combinatorial and analytic behavior

DOI10.1137/18M1220856MaRDI QIDQ5243172zbMATH OpenOpenAlexFDO

Authors Stephen Melczer, Mark C. Wilson

Publication date 15 November 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.06170

zbMATH Keywords

generating functionkernel methodanalytic combinatorics in several variableslattice path enumerationD-finite

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Abstract: We consider the enumeration of walks on the non-negative lattice $mathbb{N}^d$, with steps defined by a set $mathcalSsubset{-1,0,1}^{d}setminusmathbf0$. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps $mathcalS$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions with non-smooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of analytic combinatorics in several variables. One application is a closed form for asymptotics of models defined by step sets which are symmetric over all but one axis. As a special case, we apply our results when $d=2$ to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given.

Recommendations

• Asymptotics of lattice walks via analytic combinatorics in several variables
• The asymptotics of reflectable weighted walks in arbitrary dimension
• Riordan matrices and higher-dimensional lattice walks

Cites work

• scientific article; zbMATH DE number 4136093 (Why is no real title available?)
• scientific article; zbMATH DE number 3681764 (Why is no real title available?)
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 1300856 (Why is no real title available?)
• scientific article; zbMATH DE number 3340561 (Why is no real title available?)
• A human proof of Gessel's lattice path conjecture
• A probabilistic method for lattice path enumeration
• An elementary solution of Gessel's walks in the quadrant
• Analytic combinatorics
• Analytic combinatorics in several variables.
• Andre's reflection proof generalized to the many-candidate ballot problem
• Asymptotics for the number of walks in a Weyl chamber of type \(B\)
• Asymptotics of Multivariate Sequences II: Multiple Points of the Singular Variety
• Asymptotics of coefficients of multivariate generating functions: Improvements for smooth points
• Asymptotics of lattice walks via analytic combinatorics in several variables
• Asymptotics of multivariate sequences. I: Smooth points of the singular variety
• Automatic Classification of Restricted Lattice Walks
• Basic analytic combinatorics of directed lattice paths
• Classifying lattice walks restricted to the quarter plane
• Counting walks with large steps in an orthant
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
• Lattice path combinatorics and asymptotics of multiplicities of weights in tensor powers
• Lattice path enumeration
• Linear recurrences with constant coefficients: The multivariate case
• Non-D-finite excursions in the quarter plane
• On 3-dimensional lattice walks confined to the positive octant
• On the exit time from a cone for random walks with drift
• On the functions counting walks with small steps in the quarter plane
• Proof of Ira Gessel's lattice path conjecture
• Random Walk in a Weyl Chamber
• Random walks in Weyl chambers and the decomposition of tensor powers
• Random walks in cones
• Random walks in cones: the case of nonzero drift
• Singularity analysis via the iterated kernel method
• Some exact asymptotics in the counting of walks in the quarter plane
• The complete generating function for Gessel walks is algebraic
• The diagonal of a D-finite power series is D-finite
• Walks confined in a quadrant are not always D-finite
• Walks in the quarter plane: Kreweras' algebraic model
• Walks with small steps in the quarter plane
• Weighted lattice walks and universality classes

Cited in

(12)

• Coefficient asymptotics of algebraic multivariable generating functions
• Riordan matrices and higher-dimensional lattice walks
• Asymptotic enumeration of lonesum matrices
• Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
• On the algebraic area of lattice walks and the Hofstadter model
• Combinatorics of nondeterministic walks of the Dyck and Motzkin type
• Asymptotics of lattice walks via analytic combinatorics in several variables
• INTERACTING QUARTER-PLANE LATTICE WALK PROBLEMS: SOLUTIONS AND PROOFS
• Asymptotics for the number of walks in a Weyl chamber of type \(B\)
• The asymptotics of reflectable weighted walks in arbitrary dimension
• The asymptotics of reflectable weighted walks in arbitrary dimension
• scientific article; zbMATH DE number 10643 (Why is no real title available?)

This page was built for publication: Higher dimensional lattice walks: connecting combinatorial and analytic behavior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5243172)