Higher dimensional lattice walks: Connecting combinatorial and analytic behavior. Melczer, S. & Wilson, M. C. SIAM Journal on Discrete Mathematics, 33(4):2140-2174, Society for Industrial and Applied Mathematics, 2019. ![Higher dimensional lattice walks: Connecting combinatorial and analytic behavior [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper Slides abstract bibtex 2 downloads We consider the enumeration of walks on the non-negative lattice $ℕ^d$, with steps defined by a set $\mathcal{S} ⊂ \{ -1, 0, 1 \}^d ∖ \{\mathbf{0}\}$. 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 $\mathcal{S}$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function 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 having 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 that 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.
@Article{melczer2019higher,
author = {Melczer, Stephen and Wilson, Mark C.},
title = {Higher dimensional lattice walks: Connecting combinatorial and analytic behavior},
number = {4},
pages = {2140-2174},
volume = {33},
abstract = {We consider the enumeration of walks on the non-negative lattice
$\mathbb{N}^d$, with steps defined by a set $\mathcal{S} \subset \{ -1,
0, 1 \}^d \setminus \{\mathbf{0}\}$. 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 $\mathcal{S}$ is
symmetric over every axis; in this setting one can always apply the
methods of ACSV to a multivariate rational function 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 having 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 that 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.},
journal = {SIAM Journal on Discrete Mathematics},
keywords = {ACSV applications},
publisher = {Society for Industrial and Applied Mathematics},
url_paper = {https://arxiv.org/abs/1810.06170},
url_slides = {https://www.youtube.com/watch?v=o5SOHJbGO4g},
year = {2019},
}
Downloads: 2
{"_id":"iss65G9TceNyzsJ5e","bibbaseid":"melczer-wilson-higherdimensionallatticewalksconnectingcombinatorialandanalyticbehavior-2019","author_short":["Melczer, S.","Wilson, M. C."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Melczer"],"firstnames":["Stephen"],"suffixes":[]},{"propositions":[],"lastnames":["Wilson"],"firstnames":["Mark","C."],"suffixes":[]}],"title":"Higher dimensional lattice walks: Connecting combinatorial and analytic behavior","number":"4","pages":"2140-2174","volume":"33","abstract":"We consider the enumeration of walks on the non-negative lattice $ℕ^d$, with steps defined by a set $\\mathcal{S} ⊂ \\{ -1, 0, 1 \\}^d ∖ \\{\\mathbf{0}\\}$. 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 $\\mathcal{S}$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function 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 having 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 that 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.","journal":"SIAM Journal on Discrete Mathematics","keywords":"ACSV applications","publisher":"Society for Industrial and Applied Mathematics","url_paper":"https://arxiv.org/abs/1810.06170","url_slides":"https://www.youtube.com/watch?v=o5SOHJbGO4g","year":"2019","bibtex":"@Article{melczer2019higher,\n author = {Melczer, Stephen and Wilson, Mark C.},\n title = {Higher dimensional lattice walks: Connecting combinatorial and analytic behavior},\n number = {4},\n pages = {2140-2174},\n volume = {33},\n abstract = {We consider the enumeration of walks on the non-negative lattice\n$\\mathbb{N}^d$, with steps defined by a set $\\mathcal{S} \\subset \\{ -1,\n0, 1 \\}^d \\setminus \\{\\mathbf{0}\\}$. Previous work in this area has\nestablished asymptotics for the number of walks in certain families of\nmodels by applying the techniques of analytic combinatorics in several\nvariables (ACSV), where one encodes the generating function of a lattice\npath model as the diagonal of a multivariate rational function. Melczer\nand Mishna obtained asymptotics when the set of steps $\\mathcal{S}$ is\nsymmetric over every axis; in this setting one can always apply the\nmethods of ACSV to a multivariate rational function whose set of\nsingularities is a smooth manifold (the simplest case). Here we go\nfurther, providing asymptotics for models with generating functions that\nmust be encoded by multivariate rational functions having non-smooth\nsingular sets. In the process, our analysis connects past work to\ndeeper structural results in the theory of analytic combinatorics in\nseveral variables. One application is a closed form for asymptotics of\nmodels defined by step sets that are symmetric over all but one axis. As\na special case, we apply our results when $d=2$ to give a rigorous proof\nof asymptotics conjectured by Bostan and Kauers; asymptotics for walks\nreturning to boundary axes and the origin are also given.},\n journal = {SIAM Journal on Discrete Mathematics},\n keywords = {ACSV applications},\n publisher = {Society for Industrial and Applied Mathematics},\n url_paper = {https://arxiv.org/abs/1810.06170},\n url_slides = {https://www.youtube.com/watch?v=o5SOHJbGO4g},\n year = {2019},\n}\n\n","author_short":["Melczer, S.","Wilson, M. C."],"key":"melczer2019higher","id":"melczer2019higher","bibbaseid":"melczer-wilson-higherdimensionallatticewalksconnectingcombinatorialandanalyticbehavior-2019","role":"author","urls":{" paper":"https://arxiv.org/abs/1810.06170"," slides":"https://www.youtube.com/watch?v=o5SOHJbGO4g"},"keyword":["ACSV applications"],"metadata":{"authorlinks":{}},"downloads":2},"bibtype":"article","biburl":"https://drive.google.com/uc?export=download&id=1NEXsxwRAx2CWt43v0y0jyZdP1LdOS_xF","dataSources":["yx9ivfGLzvFNsg4LH","QdFdNQZBZSvbPbp7t","o2FBsFrZMS3PxguCG","SjBh38uzaGjRinwq8","M2T285kj8vXfTkGDx","2zimNJgtWEiEM2L3J","TAyBmAZAcnenc4YET","BCqQErP8wgW48bwvt","YjweTJPHHEQ85Pems"],"keywords":["acsv applications"],"search_terms":["higher","dimensional","lattice","walks","connecting","combinatorial","analytic","behavior","melczer","wilson"],"title":"Higher dimensional lattice walks: Connecting combinatorial and analytic behavior","year":2019,"downloads":2}