LGV scheme for lattice paths that move in non-unit spatial positive steps

Question

In the Lindström–Gessel–Viennot lemma (LGV) applied to the $Z^2$-lattice paths are taken to move in unit spatial-steps in unit time (see here).

What do we mean by "time"? In the language of LGV, we first fix positive integer $T$ and then set the weight of any path to be:

$$w(P)=\prod_{k=1}^{T}w(e_{k}),$$ where $P=(e_{1},e_{2},...,e_{T})$ and $e_{i}$ are diagonal edges as above.

However, there are applications (here on pg.3 and here on pg.14) where a version of LGV still "applies"(i.e. the LGV is used as an analogy) even though the paths are jumping in varying non-unit positive increments at each unit step time. In other words, a lattice path might jump two positive integers at time t: $P(t+1)-P(t)=2$ and three positive integers at some other time s: $P(s+1)-P(s)=3$. Here we still have a weight of a path $$w(P)=\prod_{k=1}^{T-1}w(P(k),P(k+1)),$$ where $P=(P(1),P(2),...,P(T))$ and $P(i)$ is the position of the path at time t=i. For example, in the application here they take it to be an indicator $$w(P(k),P(k+1))=1_{P(k+1)\geq P(k)}.$$

Note: The up-left motion of the paths is not really an issue actually because as mentioned we can instead consider the weights $w(P(n),P(n+1)):= 1\{ P(n)\geq P(n+1) \}$. (as opposed to having weight 1). So we are back in the forwards and backwards motion but still non-unit steps.

So it would be interesting to read of work done in LGV/Vicious-walkers and its generalizations that possibly include non-unit step. Of course, once one drops the unit-step requirement, one must also work with a more general definition of "intersection": if the weights are of the above form $w(P(k),P(k+1))$, then two paths $P_{1},P_{2}$ might intersect at a vertex $v_{*}$ such that $$P_{1}(k)=v_{*}\neq P_{2}(k)$$ and so in the LGV proof, we won't be able to swap weights.

I was thinking maybe with the bijection to Young Tableaux, one can obtain a generalization in the Young Tableaux side even though there is no corresponding object at the Vicious walkers side.

Answer 1

I still find your exact question here to be a bit difficult to suss out.

But here is one observation that might help you: what is depicted in the "Figure 2" in your post is a valid planar directed network to which the usual LGV applies, and it does represent the kind of walks you are interested in where at each "time step" the paths may advance multiple unit increments. The point is that, as the caption says, the edges are directed to the left, and to the up-left, so that in a unit time step the path takes some number (possibly zero) left steps and then takes an up-left step (up is the direction of time here). So in a single time step you can advance multiple spatial units. The catch is: in this model, you are only allowed to take forward spatial increments; whereas in the model in your "Figure 1," the spatial movements can be forward or backwards, although they are always single units at each time step.

Answer 2

The LGV lemma does not really require nodes to lie in a plane. In fact the statement is very simple without any geometric assumptions on the nodes. The role of the spatial arrangement of nodes is usually to make evident the crossing condition. Here is the simplest formulation of the LGV lemma, which I learned from Prof. Viennot in his lectures at IMSc:

Let $R$ be a commutative ring, and let $S$ be any set. Let $v:S\times S\to R$ be any function (called the weight function). Given any $s,t\in S$, a path from $s$ to $t$ is a sequence $\omega=(s=s_0,s_1,\dotsc,s_n=t)$ of distinct points in $S$. Write $\omega:s\to t$ to signify that $\omega$ is a path from $s$ to $t$. The weight of this path is defined by $$ v(\omega) = v(s_0,s_1)v(s_1,s_2)\dotsb v(s_{n-1},s_n). $$

Crossing paths

Two paths $\omega=(s_0,\dotsc,s_n)$ and $\eta=(t_0,\dotsc,t_m)$ are said to cross if $s_i=t_j$ for some $0\leq i\leq n$ and $0\leq j\leq m$.

The main hypthesis of the LGV lemma is the crossing condition:

Crossing condition

A collection of points $A_1,\dotsc,A_k, B_1,\dotsc, B_k$ is said to satisfy the crossing condition if, whenever $1\leq i<j\leq k$ and $1\leq i'<j'\leq k$, $\omega$ is a path from $i$ to $j'$ such that $v(\omega)\neq 0$ and $\eta$ is a path from $j$ to $i'$ such that $v(\eta)\neq 0$, then $\omega$ and $\eta$ cross.

Assume that, for any $1\leq i,j,\leq k$, the number of paths from $A_i$ to $B_j$ is finite. Define $$ a_{ij} = \sum_{\omega:A_i\to B_j} v(\omega). $$

Then $$ \det(a_{ij}) = \sum_{\omega_i:A_i\to B_i} v(\omega), $$ the sum being over all collections $\omega_i:A_i\to B_i$, $i=1,\dotsc,k$ of pairwise non-crossing paths.

The proof of this version is no harder than that of any other version of the LGV lemma, a sign-reversing cancellation. I used this version in my notes on Schur polynomials.