The Kernel-Method and Automated Positive-Part-Extraction
Sprache des Vortragstitels:
Englisch
Original Kurzfassung:
A lattice walk is a sequence $P_0, P_1,\dots, P_n$ of points in $\mathbb{N}^d$. The points $P_0$ and $P_n$ are its starting and end point, respectively, $n$ is its length, and the consecutive differences $P_{i+1} ? P_i$
are its steps. Fixing a starting point $P$ and a set $S$ of admissible steps combinatorialists ask for the number of walks in $\mathbb{N}^d$ that start at $P$, consist of $n$ steps, all taken from $S$, and end at $Q$: Are there nice formulas for these numbers? What is their asymptotics as $n$ goes to infinity? In answering these questions it is helpful to study the associated generating function and the functional equation it satisfies and to decide whether it satisfies a linear differential
equation with polynomial coefficients or not. Mishna and Bousquet-Mélou initiated a systematic study of this problem for walks restricted to $\mathbb{N}^2$ whose steps are taken from a subset $S$ of $\{?1,0,1\}^2$ and introduced a method involving elementary power series
algebra for proving D-finiteness of the generating functions of some instances of this problem. Bousquet-Mélou et al. generalized it to walks with steps not necessarily restricted
to $\{?1,0,1}^2$. We show how this method can be extended and automatized using Gröbner bases and a generalized Newton-Puiseux algorithm.
Forschungs-