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

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.

• The usual formulation of LGV I know of does not involve "time" in any way. It just concerns tuples of nointersecting paths in directed graphs (usually planar directed graphs, to be most useful). Maybe you can say more. Nov 27 '20 at 5:55
• Where are you seeing versions of LGV in the references you've cited? Nov 27 '20 at 11:33
• Ah, much better! So you're asking for an explanation of results that look like they follow from LGV but don't because paths can jump past nodes. Something similar is secretly happening with the Jacobi-Trudi-like formulas for dual stable Grothendieck polynomials ( arxiv.org/abs/2008.12000 ), at least if you try to approach them the LGV way. Amanov and Yeliussizov have a proof of one of these formulas ( arxiv.org/abs/2003.03907 ) that uses some kind of more sophisticated variant of LGV (too sophisticated for me, I'm afraid). Nov 27 '20 at 23:29
• @darijgrinberg thank you. At least in the Kim paper, can you point me to some part where the similar issue happens of "jumping past nodes" in the language of partitions as in Kim's paper ? Nov 29 '20 at 5:55
• The Kim paper doesn't talk about lattice paths, but if you try to prove the Jacobi-Trudi formula he proves there through LGV instead, you'll naturally get lattice paths with jumping past points. His previous paper actually uses this kind of argument. The reason why it doesn't explicitly appear anywhere is that no one has made it to work directly. Nov 29 '20 at 11:51

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 and $$1\leq i', $$\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.

• the issue in our setting is that we need time simply because the weight function only has T products. In other words, the situation is reverse: we first start with the weights and then sum over paths. So in the above, we would have to fix n=T. So all the paths are forced to have n-steps. Nov 29 '20 at 6:24
• That is why the usual LGV lemma doesn't apply i.e. we are not summing over generic paths, we are summing over paths of fixed number of T-steps. Nov 29 '20 at 6:27
• So to be clear this doesn't answer the question because as mentioned we are not in the usual LGV setting where variables n,m can vary. Nov 29 '20 at 6:35

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.

• The usual LGV doesn't apply because the weights are already fixed to have T-number of factors. Nov 29 '20 at 22:18
• So we might "miss" the intersection. In other words, two paths could intersect at a vertex not included in the weights. Therefore, we won't be able to do the involution switch as in the LGV proof. Nov 29 '20 at 22:22
• The up-left is not really an issue actually because as mentioned in the post 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. Nov 29 '20 at 22:25
• I don't understand what you mean by "two paths could intersect at a vertex not included in the weights" Nov 29 '20 at 22:49
• I would suggest you study the network in Figure 2 and try to give a combinatorial interpretation of what (weighted) nonintersecting lattice paths in it are. Nov 29 '20 at 23:08