Mathematics – Combinatorics
Scientific paper
2001-04-10
Mathematics
Combinatorics
31 pages
Scientific paper
Let S be a finite subset of Z^2. A walk on the slit plane with steps in S is a sequence (0,0)=w_0, w_1, ..., w_n of points of Z^2 such that w_{i+1}-w_i belongs to S for all i, and none of the points w_i, i>0, lie on the half-line H= {(k,0): k =< 0}. In a recent paper, G. Schaeffer and the author computed the length generating function S(t) of walks on the slit plane for several sets S. All the generating functions thus obtained turned out to be algebraic: for instance, on the ordinary square lattice, S(t) =\frac{(1+\sqrt{1+4t})^{1/2}(1+\sqrt{1-4t})^{1/2}}{2(1-4t)^{3/4}}. The combinatorial reasons for this algebraicity remain obscure. In this paper, we present two new approaches for solving slit plane models. One of them simplifies and extends the functional equation approach of the original paper. The other one is inspired by an argument of Lawler; it is more combinatorial, and explains the algebraicity of the product of three series related to the model. It can also be seen as an extension of the classical cycle lemma. Both methods work for any set of steps S. We exhibit a large family of sets S for which the generating function of walks on the slit plane is algebraic, and another family for which it is neither algebraic, nor even D-finite. These examples give a hint at where the border between algebraicity and transcendence lies, and calls for a complete classification of the sets S.
No associations
LandOfFree
Walks on the slit plane: other approaches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Walks on the slit plane: other approaches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Walks on the slit plane: other approaches will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-534590