Return to 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".

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.

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.

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".

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.

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".

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.

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)}.$$

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".

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.

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".

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.