Walks obeying two-step rules on the square lattice: full, half and quarter planes

DOI10.37236/10007zbMATH Open1481.05009arXiv2010.06955OpenAlexW3092673222MaRDI QIDQ2073308FDOQ2073308

Nicholas R. Beaton

Publication date: 1 February 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider walks on the edges of the square lattice $mathbb{Z}^2$ which obey emph{two-step rules,} which allow (or forbid) steps in a given direction to be followed by steps in another direction. We classify these rules according to a number of criteria, and show how these properties affect their generating functions, asymptotic enumerations and limiting shapes, on the full lattice as well as the upper half plane. For walks in the quarter plane, we only make a few tentative first steps. We propose candidates for the group of a model, analogous to the group of a regular short-step quarter plane model, and investigate which models have finite versus infinite groups. We demonstrate that the orbit sum method used to solve a number of the original models can be made to work for some models here, producing a D-finite solution. We also generate short series for all models and guess differential or algebraic equations where possible. In doing so, we find that there are possibilities here which do not occur for the regular short-step models, including cases with algebraic or D-finite generating functions but infinite groups, as well as models with non-D-finite generating functions but finite groups.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

lattice walkssmall steps modeltwo-step rules

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ore Polynomials in Sage
• 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
• Walks with small steps 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
• An elementary solution of Gessel's walks in the quadrant
• Unzerlegbare, nicht negative Matrizen
• Proof of Ira Gessel's lattice path conjecture
• The kernel method: a collection of examples
• Wielandt's proof of the exponent inequality for primitive nonnegative matrices
• On the symmetry classes of planar self-avoiding walks
• On anisotropic spiral self-avoiding walks

Cited In (6)

• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Enumeration of corner polyhedra and 3-connected Schnyder labelings
• Enumeration of corner polyhedra and 3-connected Schnyder labelings
• Exact solution of some quarter plane walks with interacting boundaries
• Classifying lattice walks restricted to the quarter plane
• INTERACTING QUARTER-PLANE LATTICE WALK PROBLEMS: SOLUTIONS AND PROOFS

Uses Software

• SageMath
• GitHub

This page was built for publication: Walks obeying two-step rules on the square lattice: full, half and quarter planes

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