Paths must cross in Lindström-Gessel-Viennot on the lattice

The following question (which I am going to answer myself) serves to close a little gap in some combinatorial proofs that use the Lindström--Gessel--Viennot lemma. Namely, I will show a little lemma, which is mostly used tacitly. Roughly speaking, the lemma says that if $p$ and $p^{\prime}$ are two lattice paths (using north and east steps only) in $\mathbb{Z}^{2}$ such that the starting point of $p^{\prime}$ lies weakly northwest of the starting point of $p$ but the ending point of $p$ lies weakly northwest of the ending point of $p^{\prime}$, then $p$ and $p^{\prime}$ must have a point in common. (I shall state this formally in Lemma 1 below.) See also Proposition 2 for how this result gets used. The lemma may appear rather intuitive (it is similar to the fact that the game of Hex cannot end in a draw), but the short geometric arguments would be a pain to formalize, so I will prove it combinatorially.

Basic definitions and Lemma 1

The lattice shall mean the (infinite) directed graph whose vertices are all pairs of integers (that is, its vertex set is $\mathbb{Z}^{2}$), and whose arcs are \begin{align*} \left( i,j\right) & \rightarrow\left( i,j+1\right) \qquad\text{for all }\left( i,j\right) \in\mathbb{Z}^2 \text{,} \qquad \text{and}\\ \left( i,j\right) & \rightarrow\left( i+1,j\right) \qquad\text{for all }\left( i,j\right) \in\mathbb{Z}^2 \text{.} \end{align*} The arcs of the first kind are called north-steps, whereas the arcs of the second kind are called east-steps. The vertices of the lattice will just be called vertices. We draw the lattice as the usual integer lattice in the Cartesian plane.

For each vertex $v=\left( i,j\right)$, we set $\operatorname*{x}\left( v\right) =i$ and $\operatorname*{y}\left( v\right) =j$. We refer to $\operatorname*{x}\left( v\right)$ as the x-coordinate of $v$, and to $\operatorname*{y}\left( v\right)$ as the y-coordinate of $v$.

A path will simply mean a (directed) path in the lattice.

Lemma 1. Let $A$, $B$, $A^{\prime}$ and $B^{\prime}$ be four vertices such that \begin{align*} \operatorname*{x}\left( A^{\prime}\right) & \leq\operatorname*{x}\left( A\right) ,\qquad\operatorname*{y}\left( A^{\prime}\right) \geq \operatorname*{y}\left( A\right) ,\\ \operatorname*{x}\left( B^{\prime}\right) & \leq\operatorname*{x}\left( B\right) ,\qquad\operatorname*{y}\left( B^{\prime}\right) \geq \operatorname*{y}\left( B\right) . \end{align*} Let $p$ be a path from $A$ to $B^{\prime}$. Let $p^{\prime}$ be a path from $A^{\prime}$ to $B$. Then, $p$ and $p^{\prime}$ have a vertex in common.

See Fig. 1 for an illustration of Lemma 1.

Non-intersecting lattice paths and Proposition 2

Now, fix a nonnegative integer $k$. Let $\left[ k\right]$ be the set $\left\{ 1,2,\ldots,k\right\}$. Let $\mathfrak{S}_{k}$ be the group of all permutations of $\left[ k\right]$.

A $k$-vertex shall mean a $k$-tuple of vertices. If $\mathbf{v} =\left( A_{1},A_{2},\ldots,A_{k}\right)$ is a $k$-vertex, and if $\sigma \in\mathfrak{S}_{k}$, then $\sigma\left( \mathbf{v}\right)$ denotes the $k$-vertex $\left( A_{\sigma\left( 1\right) },A_{\sigma\left( 2\right) },\ldots,A_{\sigma\left( k\right) }\right)$.

If $\left( A_{1},A_{2},\ldots,A_{k}\right)$ and $\left( B_{1},B_{2} ,\ldots,B_{k}\right)$ are two $k$-vertices, then a NILP from $\left( A_{1},A_{2},\ldots,A_{k}\right)$ to $\left( B_{1},B_{2} ,\ldots,B_{k}\right)$ shall mean a $k$-tuple $\left( p_{1},p_{2} ,\ldots,p_{k}\right)$ of paths such that

• each $p_{i}$ is a path from $A_{i}$ to $B_{i}$;

• no two of the paths $p_{1},p_{2},\ldots,p_{k}$ have a vertex in common.

("NILP" stands for "non-intersecting lattice paths", but note that the paths must neither cross nor touch.)

See Fig. 2 for an example of a NILP (with $k = 3$). Fig. 2: a NILP with $k = 3$.

If $\mathbf{u}$ and $\mathbf{v}$ are two $k$-vertices, then $N\left( \mathbf{u},\mathbf{v}\right)$ denotes the set of all NILPs from $\mathbf{u}$ to $\mathbf{v}$.

A pair $\left( \mathbf{u},\mathbf{v}\right)$ of two $k$-vertices $\mathbf{u}$ and $\mathbf{v}$ is said to be nonpermutable if and only if every $\sigma\in\mathfrak{S}_{k}$ satisfying $\sigma\neq\operatorname*{id}$ satisfies $N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) =\varnothing$. Note that we are not requiring that $N\left( \mathbf{u} ,\mathbf{v}\right) \neq\varnothing$ here.

Proposition 2. Let $\mathbf{u}=\left( A_{1},A_{2},\ldots,A_{k}\right)$ and $\mathbf{v}=\left( B_{1},B_{2},\ldots,B_{k}\right)$ be two $k$-vertices such that \begin{align*} \operatorname*{x}\left( A_{1}\right) & \geq\operatorname*{x}\left( A_{2}\right) \geq\cdots\geq\operatorname*{x}\left( A_{k}\right) ;\\ \operatorname*{y}\left( A_{1}\right) & \leq\operatorname*{y}\left( A_{2}\right) \leq\cdots\leq\operatorname*{y}\left( A_{k}\right) ;\\ \operatorname*{x}\left( B_{1}\right) & \geq\operatorname*{x}\left( B_{2}\right) \geq\cdots\geq\operatorname*{x}\left( B_{k}\right) ;\\ \operatorname*{y}\left( B_{1}\right) & \leq\operatorname*{y}\left( B_{2}\right) \leq\cdots\leq\operatorname*{y}\left( B_{k}\right) . \end{align*} Then, the pair $\left( \mathbf{u},\mathbf{v}\right)$ is nonpermutable.

Note that the situation of Proposition 2 is illustrated on Fig. 2.

What is this for?

Here is why Proposition 2 is useful. Let $R$ be a commutative ring. Assume that for each arc $a$ of the lattice, some element $\omega_{a}\in R$ is given. We call this element $\omega_{a}$ the weight of $a$. If $p$ is any path, then we let $\omega\left( p\right)$ be the product of the weights $\omega_{a}$ over all arcs $a$ of $p$. If $\mathbf{p}=\left( p_{1} ,p_{2},\ldots,p_{k}\right)$ is a NILP from a $k$-vertex $\mathbf{u}$ to a $k$-vertex $\mathbf{v}$, then we define the weight $\omega\left( \mathbf{p}\right)$ of this NILP $\mathbf{p}$ to be the product $\prod _{i=1}^{k}\omega\left( p_{i}\right)$.

If $A$ and $B$ are two vertices, then $N\left( A,B\right)$ shall denote the set of all paths from $A$ to $B$.

Now, recall that the lattice (as a directed graph) is acyclic. Hence, the Lindström--Gessel--Viennot lemma yields:

Theorem 3. Let $\mathbf{u}=\left( A_{1},A_{2},\ldots,A_{k}\right)$ and $\mathbf{v}=\left( B_{1},B_{2},\ldots,B_{k}\right)$ be two $k$-vertices. Then, \begin{align*} \det\left( \left( \sum_{p\in N\left( A_{i},B_{j}\right) }\omega\left( p\right) \right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) & =\sum_{\sigma\in\mathfrak{S}_{k}}\left( -1\right) ^{\sigma}\sum _{\mathbf{p}\in N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) }\omega\left( \mathbf{p}\right) . \end{align*} (Here, $\left( -1\right) ^{\sigma}$ denotes the sign of the permutation $\sigma$.)

If a pair $\left( \mathbf{u},\mathbf{v}\right)$ of two $k$-vertices is nonpermutable, then the sum on the right hand side of Theorem 3 can be simplified, as only one of its terms (if any) is nonzero. This, and Proposition 2, leads to the following fact:

Corollary 4. Let $\mathbf{u}=\left( A_{1},A_{2},\ldots,A_{k}\right)$ and $\mathbf{v}=\left( B_{1},B_{2},\ldots,B_{k}\right)$ be two $k$-vertices such that \begin{align*} \operatorname*{x}\left( A_{1}\right) & \geq\operatorname*{x}\left( A_{2}\right) \geq\cdots\geq\operatorname*{x}\left( A_{k}\right) ;\\ \operatorname*{y}\left( A_{1}\right) & \leq\operatorname*{y}\left( A_{2}\right) \leq\cdots\leq\operatorname*{y}\left( A_{k}\right) ;\\ \operatorname*{x}\left( B_{1}\right) & \geq\operatorname*{x}\left( B_{2}\right) \geq\cdots\geq\operatorname*{x}\left( B_{k}\right) ;\\ \operatorname*{y}\left( B_{1}\right) & \leq\operatorname*{y}\left( B_{2}\right) \leq\cdots\leq\operatorname*{y}\left( B_{k}\right) . \end{align*} Then, \begin{align*} \det\left( \left( \sum_{p\in N\left( A_{i},B_{j}\right) }\omega\left( p\right) \right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) =\sum _{\mathbf{p}\in N\left( \mathbf{u},\mathbf{v}\right) }\omega\left( \mathbf{p}\right) . \end{align*}

When people apply the Lindström--Gessel--Viennot lemma to the lattice and don't get an alternating sum like in Theorem 3, they are usually applying Corollary 4. For example, this is what is being done in the classical proof of the Jacobi--Trudi identities using Lindström--Gessel--Viennot.

So here are proofs of Lemma 1, Proposition 2 and Corollary 4. I will not prove Theorem 3, since it is the classical Lindström--Gessel--Viennot lemma and has various proofs easily accessible (see, e.g., its Wikipedia page or the proof of Theorem 1 in Ira Gessel and X. G. Viennot, Determinants, Paths, and Plane Partitions).

Proof of Lemma 1

We shall first give a combinatorial proof of Lemma 1 that is completely rigorous and self-contained but rather dull and long. Then, we will sketch a second proof that relies on geometric intuition, as well as a third proof that serves as a sort of compromise between the first two (it is combinatorial and simpler than the first one, though formalizing it would be more laborious).

First proof of Lemma 1.

If $q$ is any path, then the length $\ell\left( q\right)$ of $q$ is defined to be the number of arcs of $q$.

We shall now prove Lemma 1 by strong induction on $\ell\left( p\right) +\ell\left( p^{\prime}\right)$:

Induction step: Fix a nonnegative integer $N$. Assume (as the induction hypothesis) that Lemma 1 holds whenever $\ell\left( p\right) +\ell\left( p^{\prime}\right) <N$. We must now prove that Lemma 1 holds when $\ell\left( p\right) +\ell\left( p^{\prime}\right) =N$.

So let $A$, $B$, $A^{\prime}$, $B^{\prime}$, $p$ and $p^{\prime}$ be as in Lemma 1, and let us assume that $\ell\left( p\right) +\ell\left( p^{\prime }\right) =N$. We must prove that $p$ and $p^{\prime}$ have a vertex in common.

Assume the contrary. Thus, $p$ and $p^{\prime}$ have no vertex in common.

The vertex $A$ belongs to the path $p$, and thus does not belong to the path $p^{\prime}$ (since $p$ and $p^{\prime}$ have no vertex in common). Similarly, the vertex $A^{\prime}$ does not belong to the path $p$.

Recall that each arc of the lattice is either an east-step or a north-step. Thus, the x-coordinates of the vertices of a path are always weakly increasing, and so are the y-coordinates. Hence, the existence of a path $p$ from $A$ to $B^{\prime}$ shows that $\operatorname{x}\left( A\right) \leq\operatorname{x}\left( B^{\prime}\right)$ and $\operatorname{y} \left( A\right) \leq\operatorname{y}\left( B^{\prime}\right)$. Similarly, the existence of a path $p^{\prime}$ from $A^{\prime}$ to $B$ yields $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x} \left( B\right)$ and $\operatorname{y}\left( A^{\prime}\right) \leq\operatorname{y}\left( B\right)$.

Next, we claim that $\ell\left( p\right) \neq0$.

[Proof: Assume the contrary. Thus, $\ell\left( p\right) =0$. Hence, the path $p$ has no steps. Therefore, $A=B^{\prime}$ (since $p$ is a path from $A$ to $B^{\prime}$). Hence, $\operatorname{y}\left( A\right) =\operatorname{y}\left( B^{\prime}\right) \geq\operatorname{y}\left( B\right)$, so that $\operatorname{y}\left( A^{\prime}\right) \geq\operatorname{y}\left( A\right) \geq\operatorname{y}\left( B\right)$. Combining this with $\operatorname{y}\left( A^{\prime}\right) \leq\operatorname{y}\left( B\right)$, we obtain $\operatorname{y}\left( A^{\prime}\right) =\operatorname{y}\left( B\right)$. Combining $\operatorname{y}\left( A^{\prime}\right) \geq\operatorname{y}\left( A\right)$ with $\operatorname{y}\left( A^{\prime}\right) =\operatorname{y}\left( B\right) \leq\operatorname{y}\left( A\right)$, we obtain $\operatorname{y}\left( A^{\prime}\right) =\operatorname{y} \left( A\right)$. Thus, $\operatorname{y}\left( A\right) =\operatorname{y}\left( A^{\prime}\right) =\operatorname{y}\left( B\right)$. Therefore, the vertex $A$ lies on the horizontal line that contains $A^{\prime}$ and $B$. Furthermore, this vertex $A$ must lie on the line segment between $A^{\prime}$ and $B$ (since $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x}\left( \underbrace{A}_{=B^{\prime} }\right) =\operatorname{x}\left( B^{\prime}\right) \leq\operatorname{x} \left( B\right)$).

Recall again that the y-coordinates of the vertices a path are always weakly increasing. Moreover, they increase strictly whenever the path makes a north-step. Hence, if the path $p^{\prime}$ would have any north-step, then we would have $\operatorname{y}\left( A^{\prime}\right) <\operatorname{y} \left( B\right)$ (since $p^{\prime}$ is a path from $A^{\prime}$ to $B$). But this would contradict $\operatorname{y}\left( A^{\prime}\right) \geq\operatorname{y}\left( B\right)$. Hence, the path $p^{\prime}$ has no north-step. Thus, $p^{\prime}$ consists entirely of east-steps. Hence, $p^{\prime}$ contains every vertex on the line segment between $A^{\prime}$ and $B$. Therefore, $p^{\prime}$ contains the vertex $A$ (since the vertex $A$ lies on the line segment between $A^{\prime}$ and $B$). This contradicts the fact that $A$ does not belong to the path $p^{\prime}$. This contradiction shows that our assumption was false; hence, $\ell\left( p\right) \neq0$ is proven.]

Furthermore, we claim that $\ell\left( p^{\prime}\right) \neq0$.

[Proof: Assume the contrary. Thus, $\ell\left( p^{\prime}\right) =0$. Hence, the path $p^{\prime}$ has no steps. Therefore, $A^{\prime}=B$ (since $p^{\prime}$ is a path from $A^{\prime}$ to $B$). Hence, $\operatorname{x}\left( A^{\prime}\right) =\operatorname{x}\left( B\right) \geq\operatorname{x}\left( B^{\prime}\right)$, so that $\operatorname{x}\left( A\right) \geq\operatorname{x}\left( A^{\prime }\right) \geq\operatorname{x}\left( B^{\prime}\right)$. Combining this with $\operatorname{x}\left( A\right) \leq\operatorname{x}\left( B^{\prime}\right)$, we obtain $\operatorname{x}\left( A\right) =\operatorname{x}\left( B^{\prime}\right)$. Combining $\operatorname{x} \left( A\right) \geq\operatorname{x}\left( A^{\prime}\right)$ with $\operatorname{x}\left( A^{\prime}\right) \geq\operatorname{x}\left( B^{\prime}\right) =\operatorname{x}\left( A\right)$, we obtain $\operatorname{x}\left( A\right) =\operatorname{x}\left( A^{\prime }\right)$. Thus, $\operatorname{x}\left( A^{\prime}\right) =\operatorname{x}\left( A\right) =\operatorname{x}\left( B^{\prime }\right)$. Therefore, the vertex $A^{\prime}$ lies on the vertical line that contains $A$ and $B^{\prime}$. Furthermore, this vertex $A^{\prime}$ must lie on the line segment between $A$ and $B^{\prime}$ (since $\operatorname{y} \left( A^{\prime}\right) \geq\operatorname{y}\left( A\right)$ and $\operatorname{y}\left( \underbrace{A^{\prime}}_{=B}\right) =\operatorname{y}\left( B\right) \leq\operatorname{y}\left( B^{\prime }\right)$).

Recall again that the x-coordinates of the vertices a path are always weakly increasing. Moreover, they increase strictly whenever the path makes an east-step. Hence, if the path $p$ would have any east-step, then we would have $\operatorname{x}\left( A\right) <\operatorname{x}\left( B^{\prime }\right)$ (since $p$ is a path from $A$ to $B^{\prime}$). But this would contradict $\operatorname{x}\left( A\right) =\operatorname{x}\left( B^{\prime}\right)$. Hence, the path $p$ has no east-step. Thus, $p$ consists entirely of north-steps. Hence, $p$ contains every vertex on the line segment between $A$ and $B^{\prime}$. Therefore, $p$ contains the vertex $A^{\prime}$ (since the vertex $A^{\prime}$ lies on the line segment between $A$ and $B^{\prime}$). This contradicts the fact that $A^{\prime}$ does not belong to the path $p$. This contradiction shows that our assumption was false; hence, $\ell\left( p^{\prime}\right) \neq0$ is proven.]

Let $P$ be the second vertex of the path $p$. (This is well-defined, since $\ell\left( p\right) \neq0$.) Hence, $P$ lies on a path from $A$ to $B^{\prime}$ (namely, on the path $p$). Therefore, $\operatorname{x}\left( A\right) \leq\operatorname{x}\left( P\right) \leq\operatorname{x}\left( B^{\prime}\right)$ (since the x-coordinates of the vertices a path are always weakly increasing) and $\operatorname{y}\left( A\right) \leq\operatorname{y}\left( P\right) \leq\operatorname{y}\left( B^{\prime }\right)$ (since the y-coordinates of the vertices a path are always weakly increasing). Let $r$ be the path from $P$ to $B^{\prime}$ obtained by removing the first arc from $p$. Thus, $r$ is a subpath of $p$. Hence, the paths $r$ and $p^{\prime}$ have no vertex in common (since $p$ and $p^{\prime}$ have no vertex in common). Also, $\ell\left( r\right) =\ell\left( p\right) -1<\ell\left( p\right)$ and thus $\underbrace{\ell\left( r\right) }_{<\ell\left( p\right) }+\ell\left( p^{\prime}\right) <\ell\left( p\right) +\ell\left( p^{\prime}\right) =N$.

Moreover, $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x} \left( A\right) \leq\operatorname{x}\left( P\right)$. If we had $\operatorname{y}\left( A^{\prime}\right) \geq\operatorname{y}\left( P\right)$, then we could apply Lemma 1 to $P$ and $r$ instead of $A$ and $p$ (by the induction hypothesis, since $\ell\left( r\right) +\ell\left( p^{\prime}\right) <N$). We thus would conclude that the paths $r$ and $p^{\prime}$ have a vertex in common; this would contradict the fact that the paths $r$ and $p^{\prime}$ have no vertex in common. Hence, we cannot have $\operatorname{y}\left( A^{\prime}\right) \geq\operatorname{y}\left( P\right)$. Thus, $\operatorname{y}\left( A^{\prime}\right) <\operatorname{y}\left( P\right)$. Hence, $\operatorname{y}\left( A^{\prime}\right) \leq\operatorname{y}\left( P\right) -1$ (since $\operatorname{y}\left( A^{\prime}\right)$ and $\operatorname{y}\left( P\right)$ are integers).

But $P$ is the next vertex after $A$ on the path $p$. Hence, there is an arc from $A$ to $P$. If this arc was an east-step, then we would have $\operatorname{y}\left( P\right) =\operatorname{y}\left( A\right)$, which would contradict $\operatorname{y}\left( A\right) \leq \operatorname{y}\left( A^{\prime}\right) <\operatorname{y}\left( P\right)$. Hence, this arc cannot be an east-step. Thus, this arc must be a north-step. Therefore, $\operatorname{y}\left( P\right) =\operatorname{y} \left( A\right) +1$ and $\operatorname{x}\left( P\right) =\operatorname{x}\left( A\right)$. Combining $\operatorname{y}\left( A^{\prime}\right) \leq\operatorname{y}\left( P\right) -1=\operatorname{y} \left( A\right)$ (since $\operatorname{y}\left( P\right) =\operatorname{y}\left( A\right) +1$) with $\operatorname{y}\left( A^{\prime}\right) \geq\operatorname{y}\left( A\right)$, we obtain $\operatorname{y}\left( A^{\prime}\right) =\operatorname{y}\left( A\right)$.

Let $P^{\prime}$ be the second vertex on the path $p^{\prime}$. (This is well-defined, since $\ell\left( p^{\prime}\right) \neq0$.) Hence, $P^{\prime}$ lies on a path from $A^{\prime}$ to $B$ (namely, on the path $p^{\prime}$). Therefore, $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x}\left( P^{\prime}\right) \leq\operatorname{x}\left( B\right)$ (since the x-coordinates of the vertices a path are always weakly increasing) and $\operatorname{y}\left( A^{\prime}\right) \leq \operatorname{y}\left( P^{\prime}\right) \leq\operatorname{y}\left( B\right)$ (since the y-coordinates of the vertices a path are always weakly increasing). Let $r^{\prime}$ be the path from $P^{\prime}$ to $B$ obtained by removing the first arc from $p^{\prime}$. Thus, $r^{\prime}$ is a subpath of $p^{\prime}$. Hence, the paths $p$ and $r^{\prime}$ have no vertex in common (since $p$ and $p^{\prime}$ have no vertex in common). Also, $\ell\left( r^{\prime}\right) =\ell\left( p^{\prime}\right) -1<\ell\left( p^{\prime }\right)$ and thus $\ell\left( p\right) +\underbrace{\ell\left( r^{\prime}\right) }_{<\ell\left( p^{\prime}\right) }<\ell\left( p\right) +\ell\left( p^{\prime}\right) =N$.

Moreover, $\operatorname{y}\left( P^{\prime}\right) \geq\operatorname{y} \left( A^{\prime}\right) \geq\operatorname{y}\left( A\right)$. If we had $\operatorname{x}\left( P^{\prime}\right) \leq\operatorname{x}\left( A\right)$, then we could apply Lemma 1 to $P^{\prime}$ and $r^{\prime}$ instead of $A^{\prime}$ and $p^{\prime}$ (by the induction hypothesis, since $\ell\left( p\right) +\ell\left( r^{\prime}\right) <N$). We thus would conclude that the paths $p$ and $r^{\prime}$ have a vertex in common; this would contradict the fact that the paths $p$ and $r^{\prime}$ have no vertex in common. Hence, we cannot have $\operatorname{x}\left( P^{\prime}\right) \leq\operatorname{x}\left( A\right)$. Thus, $\operatorname{x}\left( P^{\prime}\right) >\operatorname{x}\left( A\right)$. Hence, $\operatorname{x}\left( P^{\prime}\right) \geq\operatorname{x}\left( A\right) +1$ (since $\operatorname{x}\left( P^{\prime}\right)$ and $\operatorname{x}\left( A\right)$ are integers).

But $P^{\prime}$ is the next vertex after $A^{\prime}$ on the path $p^{\prime }$. Hence, there is an arc from $A^{\prime}$ to $P^{\prime}$. If this arc was a north-step, then we would have $\operatorname{x}\left( P^{\prime}\right) =\operatorname{x}\left( A^{\prime}\right)$, which would contradict $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x}\left( A\right) <\operatorname{x}\left( P^{\prime}\right)$. Hence, this arc cannot be a north-step. Thus, this arc must be an east-step. Therefore, $\operatorname{y}\left( P^{\prime}\right) =\operatorname{y}\left( A^{\prime}\right)$ and $\operatorname{x}\left( P^{\prime}\right) =\operatorname{x}\left( A^{\prime}\right) +1$. Hence, $\operatorname{x} \left( A^{\prime}\right) +1=\operatorname{x}\left( P^{\prime}\right) \geq\operatorname{x}\left( A\right) +1$, so that $\operatorname{x}\left( A^{\prime}\right) \geq\operatorname{x}\left( A\right)$. Combining this with $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x}\left( A\right)$, we obtain $\operatorname{x}\left( A^{\prime}\right) =\operatorname{x}\left( A\right)$.

Now, the vertices $A$ and $A^{\prime}$ have the same x-coordinate (since $\operatorname{x}\left( A^{\prime}\right) =\operatorname{x}\left( A\right)$) and the same y-coordinate (since $\operatorname{y}\left( A^{\prime}\right) =\operatorname{y}\left( A\right)$). Hence, these two vertices are equal. In other words, $A=A^{\prime}$. Hence, the vertex $A$ belongs to the path $p^{\prime}$ (since the vertex $A^{\prime}$ belongs to the path $p^{\prime}$). This contradicts the fact that the vertex $A$ does not belong to the path $p^{\prime}$. This contradiction shows that our assumption was false. Hence, we have shown that $p$ and $p^{\prime}$ have a vertex in common.

Now, forget that we fixed $A$, $B$, $A^{\prime}$, $B^{\prime}$, $p$ and $p^{\prime}$. We thus have proven that if $A$, $B$, $A^{\prime}$, $B^{\prime}$, $p$ and $p^{\prime}$ are as in Lemma 1, and if $\ell\left( p\right) +\ell\left( p^{\prime}\right) =N$, then $p$ and $p^{\prime}$ have a vertex in common. In other words, Lemma 1 holds when $\ell\left( p\right) +\ell\left( p^{\prime}\right) =N$. This completes the induction step. Hence, Lemma 1 is proven.

Second proof of Lemma 1 (sketched). Recall that each arc of the lattice is either an east-step or a north-step. Thus, the x-coordinates of the vertices of a path are always weakly increasing, and so are the y-coordinates. Hence, the existence of a path $p$ from $A$ to $B^{\prime}$ shows that $\operatorname{x}\left( A\right) \leq\operatorname{x}\left( B^{\prime }\right)$ and $\operatorname{y}\left( A\right) \leq\operatorname{y} \left( B^{\prime}\right)$. Similarly, the existence of $p^{\prime}$ yields $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x}\left( B\right)$ and $\operatorname{y}\left( A^{\prime}\right) \leq \operatorname{y}\left( B\right)$.

Thus, \begin{align*} \operatorname{x}\left( A^{\prime}\right) & \leq\operatorname{x}\left( A\right) \leq\operatorname{x}\left( B^{\prime}\right) \leq \operatorname{x}\left( B\right) \qquad\text{and}\\ \operatorname{y}\left( A\right) & \leq\operatorname{y}\left( A^{\prime }\right) \leq\operatorname{y}\left( B\right) \leq\operatorname{y}\left( B^{\prime}\right) . \end{align*} Now, consider the rectangle (drawn in black on Fig. 3) whose four sides are given by the equations \begin{align*} x=\operatorname{x}\left( A^{\prime}\right) ,\qquad y=\operatorname{y} \left( A\right) ,\qquad x=\operatorname{x}\left( B\right) ,\qquad y=\operatorname{y}\left( B^{\prime}\right) , \end{align*} respectively (all in Cartesian coordinates). Then, the path $p$ joins two opposite sides of this rectangle (namely, the second and the fourth), whereas the path $p^{\prime}$ joins the other two sides of this rectangle; moreover, both paths stay fully within the rectangle (due to $\operatorname{x}\left( A^{\prime}\right) \leq\operatorname{x}\left( A\right) \leq \operatorname{x}\left( B^{\prime}\right) \leq\operatorname{x}\left( B\right)$ and $\operatorname{y}\left( A\right) \leq\operatorname{y} \left( A^{\prime}\right) \leq\operatorname{y}\left( B\right) \leq\operatorname{y}\left( B^{\prime}\right)$). Hence, it is geometrically obvious that $p$ and $p^{\prime}$ must meet; in other words, $p$ and $p^{\prime}$ have a vertex in common. This proves Lemma 1 (if you trust this geometric shortcut). Fig. 3: illustration for the second and third proofs of Lemma 1, showing the rectangle and the extended paths $\widetilde{p}$ and $\widetilde{p^{\prime}}$.

Third proof of Lemma 1 (sketched). Proceed as in the Second proof above, up until the "geometrically obvious" step. We are going to prove combinatorially that $p$ and $p^{\prime}$ have a vertex in common.

Indeed, assume the contrary. Hence, the paths $p$ and $p^{\prime}$ have no vertex in common.

We extend the path $p$ to a bidirectionally infinite path $\widetilde{p}$ by vertical steps (i.e., arcs of the form $\left( i,j\right) \rightarrow\left( i,j+1\right)$) in both directions (so the path $\widetilde{p}$ first reaches $A$ through infinitely many north-steps, then proceeds to $B^{\prime}$ along $p$, and then leaves $B^{\prime}$ along infinitely many north-steps). (These new steps are the dashed red steps in Fig. 3.)

We extend the path $p^{\prime}$ to a bidirectionally infinite path $\widetilde{p^{\prime}}$ by horizontal steps (i.e., arcs of the form $\left( i,j\right) \rightarrow\left( i+1,j\right)$) in both directions. (These new steps are the dashed blue steps in Fig. 3.)

The resulting infinite paths $\widetilde{p}$ and $\widetilde{p^{\prime}}$ have no vertex in common (indeed, the paths $p$ and $p^{\prime}$ stay within the rectangle discussed above, and have no vertex in common; meanwhile, the new steps we have added to them to obtain $\widetilde{p}$ and $\widetilde{p^{\prime}}$ escape this rectangle normally in four different directions, whence they intersect neither each other nor $p$ or $p^{\prime}$). Recall that each arc of the lattice is either an east-step or a north-step. Thus, if a vertex $C$ runs through a path, the value $\operatorname{x}\left( C\right) +\operatorname{y}\left( C\right)$ is incremented by $1$ with each step. Hence, if $q$ is a bidirectionally infinite path, then, for each $N\in\mathbb{Z}$, there is a unique vertex $C$ of $q$ satisfying $\operatorname{x}\left( C\right) +\operatorname{y}\left( C\right) =N$. Denote this vertex $C$ by $h_{N}\left( q\right)$. Thus, the vertices of $q$ are $\ldots,h_{-1}\left( q\right) ,h_{0}\left( q\right) ,h_{1}\left( q\right) ,\ldots$ in this order.

All sufficiently low $N\in\mathbb{Z}$ satisfy $\operatorname{x}\left( h_{N}\left( \widetilde{p^{\prime}}\right) \right) <\operatorname{x}\left( h_{N}\left( \widetilde{p}\right) \right)$, whereas all sufficiently high $N\in\mathbb{Z}$ satisfy $\operatorname{x}\left( h_{N}\left( \widetilde{p^{\prime}}\right) \right) >\operatorname{x}\left( h_{N}\left( \widetilde{p}\right) \right)$. Hence, the set of all $N\in\mathbb{Z}$ that satisfy $\operatorname{x}\left( h_{N}\left( \widetilde{p^{\prime}}\right) \right) <\operatorname{x}\left( h_{N}\left( \widetilde{p}\right) \right)$ is a nonempty set of integers that is bounded from above. Therefore, this set has a maximum. Let $M$ be this maximum. Thus, $M\in\mathbb{Z}$ satisfies $\operatorname{x}\left( h_{M}\left( \widetilde{p^{\prime}}\right) \right) <\operatorname{x}\left( h_{M}\left( \widetilde{p}\right) \right)$ but $\operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime}}\right) \right) \geq\operatorname{x}\left( h_{M+1}\left( \widetilde{p}\right) \right)$.

But the point $h_{M+1}\left( \widetilde{p^{\prime}}\right)$ is either the eastern or the northern neighbor of $h_{M}\left( \widetilde{p^{\prime} }\right)$; hence, $\operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime}}\right) \right) \leq\operatorname{x}\left( h_{M}\left( \widetilde{p^{\prime}}\right) \right) +1$. Also, the point $h_{M+1}\left( \widetilde{p}\right)$ is either the eastern or the northern neighbor of $h_{M}\left( \widetilde{p}\right)$; thus, $\operatorname{x} \left( h_{M+1}\left( \widetilde{p}\right) \right) \geq\operatorname{x} \left( h_{M}\left( \widetilde{p}\right) \right)$. Hence, \begin{align*} \operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime}}\right) \right) \leq\underbrace{\operatorname{x}\left( h_{M}\left( \widetilde{p^{\prime}}\right) \right) }_{<\operatorname{x}\left( h_{M}\left( \widetilde{p}\right) \right) }+1<\underbrace{\operatorname{x} \left( h_{M}\left( \widetilde{p}\right) \right) }_{\leq\operatorname{x} \left( h_{M+1}\left( \widetilde{p}\right) \right) }+1\leq\operatorname{x} \left( h_{M+1}\left( \widetilde{p}\right) \right) +1. \end{align*} Therefore, $\operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime} }\right) \right) \leq\operatorname{x}\left( h_{M+1}\left( \widetilde{p} \right) \right)$ (since both sides are integers). Combining this with $\operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime}}\right) \right) \geq\operatorname{x}\left( h_{M+1}\left( \widetilde{p}\right) \right)$, we obtain $\operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime}}\right) \right) =\operatorname{x}\left( h_{M+1}\left( \widetilde{p}\right) \right)$. Hence, $h_{M+1}\left( \widetilde{p^{\prime}}\right) =h_{M+1}\left( \widetilde{p}\right)$ (since $\operatorname{x}\left( h_{M+1}\left( \widetilde{p^{\prime}}\right) \right) -\operatorname{y}\left( h_{M+1}\left( \widetilde{p^{\prime} }\right) \right) =M+1=\operatorname{x}\left( h_{M+1}\left( \widetilde{p} \right) \right) -\operatorname{y}\left( h_{M+1}\left( \widetilde{p} \right) \right)$ as well). Thus, the paths $\widetilde{p}$ and $\widetilde{p^{\prime}}$ have a vertex in common (namely, $h_{M+1}\left( \widetilde{p^{\prime}}\right) =h_{M+1}\left( \widetilde{p}\right)$). This contradicts the fact that they don't. This contradiction shows that our assumption was false. Hence, the paths $p$ and $p^{\prime}$ have a vertex in common. This proves Lemma 1 again.

Proof of Proposition 2

Proof of Proposition 2. Let $\sigma\in\mathfrak{S}_{k}$ be such that $\sigma\neq\operatorname*{id}$. We shall show that $N\left( \mathbf{u} ,\sigma\left( \mathbf{v}\right) \right) =\varnothing$. Indeed, let $\mathbf{p}\in N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right)$.

The permutation $\sigma$ has at least one inversion (since $\sigma \neq\operatorname*{id}$). In other words, there exist two elements $i$ and $j$ of $\left[ k\right]$ such that $i<j$ and $\sigma\left( i\right) >\sigma\left( j\right)$. Consider such $i$ and $j$.

Write $\mathbf{p}$ in the form $\mathbf{p}=\left( p_{1},p_{2},\ldots ,p_{k}\right)$. Thus, $\left( p_{1},p_{2},\ldots,p_{k}\right)$ is a NILP from $\mathbf{u}$ to $\sigma\left( \mathbf{v}\right)$ (since $\left( p_{1},p_{2},\ldots,p_{k}\right) =\mathbf{p}\in N\left( \mathbf{u} ,\sigma\left( \mathbf{v}\right) \right)$). In other words, $\left( p_{1},p_{2},\ldots,p_{k}\right)$ is a NILP from $\left(A_1, A_2, \ldots, A_k\right)$ to $\left(B_{\sigma\left(1\right)}, B_{\sigma\left(2\right)}, \ldots, B_{\sigma\left(k\right)}\right)$ (since $\mathbf{u} = \left(A_1, A_2, \ldots, A_k\right)$ and $\sigma\left(\mathbf{v}\right) = \sigma\left(B_1, B_2, \ldots, B_k\right) = \left(B_{\sigma\left(1\right)}, B_{\sigma\left(2\right)}, \ldots, B_{\sigma\left(k\right)}\right)$). By the definition of a NILP, this implies that

• $p_{i}$ is a path from $A_{i}$ to $B_{\sigma\left( i\right) }$;

• $p_{j}$ is a path from $A_{j}$ to $B_{\sigma\left( j\right) }$;

• the paths $p_{i}$ and $p_{j}$ have no vertex in common (since $i\neq j$).

One of the assumptions of Proposition 2 was $\operatorname{x}\left( A_{1}\right) \geq\operatorname{x}\left( A_{2}\right) \geq\cdots \geq\operatorname{x}\left( A_{k}\right)$; hence, $\operatorname{x}\left( A_{i}\right) \geq\operatorname{x}\left( A_{j}\right)$ (since $i<j$), and thus $\operatorname{x}\left( A_{j}\right) \leq\operatorname{x}\left( A_{i}\right)$. Similarly, the second assumption of Proposition 2 yields $\operatorname{y}\left( A_{j}\right) \geq\operatorname{y}\left( A_{i}\right)$. Also, the third assumption of Proposition 2 says $\operatorname{x}\left( B_{1}\right) \geq\operatorname{x}\left( B_{2}\right) \geq\cdots\geq\operatorname{x}\left( B_{k}\right)$; hence, $\operatorname{x}\left( B_{\sigma\left( j\right) }\right) \geq\operatorname{x}\left( B_{\sigma\left( i\right) }\right)$ (since $\sigma\left( j\right) <\sigma\left( i\right)$), so that $\operatorname{x}\left( B_{\sigma\left( i\right) }\right) \leq\operatorname{x}\left( B_{\sigma\left( j\right) }\right)$. Similarly, the fourth assumption of Proposition 2 yields $\operatorname{y}\left( B_{\sigma\left( i\right) }\right) \geq\operatorname{y}\left( B_{\sigma\left( j\right) }\right)$. Hence, Lemma 1 (applied to $A=A_{i}$, $B=B_{\sigma\left( j\right) }$, $A^{\prime }=A_{j}$, $B^{\prime}=B_{\sigma\left( i\right) }$, $p=p_{i}$ and $p^{\prime }=p_{j}$) shows that $p_{i}$ and $p_{j}$ have a vertex in common. This contradicts the fact that the paths $p_{i}$ and $p_{j}$ have no vertex in common.

Now, forget that we fixed $\mathbf{p}$. Thus, we have found a contradiction for each $\mathbf{p}\in N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right)$. Hence, there exists no $\mathbf{p}\in N\left( \mathbf{u} ,\sigma\left( \mathbf{v}\right) \right)$. In other words, $N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) =\varnothing$.

Now, forget that we fixed $\sigma$. Thus, we have shown that every $\sigma \in\mathfrak{S}_{k}$ satisfying $\sigma\neq\operatorname*{id}$ satisfies $N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) =\varnothing$. In other words, the pair $\left( \mathbf{u},\mathbf{v}\right)$ is nonpermutable (by the definition of "nonpermutable"). This proves Proposition 2.

Proof of Corollary 4

We can finally derive Corollary 4 from Theorem 3:

Proof of Corollary 4. Proposition 2 shows that the pair $\left( \mathbf{u},\mathbf{v}\right)$ is nonpermutable. In other words, every $\sigma\in\mathfrak{S}_{k}$ satisfying $\sigma\neq\operatorname*{id}$ satisfies $N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) =\varnothing$. Hence, every $\sigma\in\mathfrak{S}_{k}$ satisfying $\sigma \neq\operatorname*{id}$ satisfies \begin{align*} \sum_{\mathbf{p}\in N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) }\omega\left( \mathbf{p}\right) =\sum_{\mathbf{p}\in\varnothing }\omega\left( \mathbf{p}\right) =\left( \text{empty sum}\right) =0. \label{1} \tag{1} \end{align*} But Theorem 3 yields \begin{align*} & \det\left( \left( \sum_{p\in N\left( A_{i},B_{j}\right) }\omega\left( p\right) \right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) \\ & =\sum_{\sigma\in\mathfrak{S}_{k}}\left( -1\right) ^{\sigma} \sum_{\mathbf{p}\in N\left( \mathbf{u},\sigma\left( \mathbf{v}\right) \right) }\omega\left( \mathbf{p}\right) \\ & =\underbrace{\left( -1\right) ^{\operatorname*{id}}}_{=1}\underbrace{\sum _{\mathbf{p}\in N\left( \mathbf{u},\operatorname*{id}\left( \mathbf{v} \right) \right) }}_{\substack{=\sum_{\mathbf{p}\in N\left( \mathbf{u} ,\mathbf{v}\right) }\\\text{(since }\operatorname*{id}\left( \mathbf{v} \right) =\mathbf{v}\text{)}}}\omega\left( \mathbf{p}\right) +\sum _{\substack{\sigma\in\mathfrak{S}_{k};\\\sigma\neq\operatorname*{id}}}\left( -1\right) ^{\sigma}\underbrace{\sum_{\mathbf{p}\in N\left( \mathbf{u} ,\sigma\left( \mathbf{v}\right) \right) }\omega\left( \mathbf{p}\right) }_{\substack{=0\\\text{(by \eqref{1}, since }\sigma\neq\operatorname*{id}\text{)}}}\\ & \qquad \left( \text{here, we have split off the addend for } \sigma = \operatorname{id} \text{ from the sum }\right) \\ & =\sum_{\mathbf{p}\in N\left( \mathbf{u},\mathbf{v}\right) }\omega\left( \mathbf{p}\right) +\underbrace{\sum_{\substack{\sigma\in\mathfrak{S} _{k};\\\sigma\neq\operatorname*{id}}}\left( -1\right) ^{\sigma}0}_{=0} =\sum_{\mathbf{p}\in N\left( \mathbf{u},\mathbf{v}\right) }\omega\left( \mathbf{p}\right) . \end{align*} This proves Corollary 4.

PS. Source code for the figures

Fig. 1, Fig. 2 and Fig. 3 were made using LaTeX and tikz; here is the source code:

\documentclass{amsart}
\usepackage{tikz,xcolor}

\definecolor{dbluecolor}{rgb}{0.01,0.02,0.7}
\definecolor{dgreencolor}{rgb}{0.2,0.4,0.0}
\definecolor{darkred}{rgb}{0.7,0,0}

\begin{document}

% Fig. 1:
\begin{figure}[t]
$\begin{tikzpicture} \draw[densely dotted] (0,0) grid (7.2,7.2); % axes: \draw[->] (0,0) -- (0,7.2); \draw[->] (0,0) -- (7.2,0); \foreach \x/\xtext in {0, 1, 2, 3, 4, 5, 6, 7} \draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {\xtext}; \foreach \y/\ytext in {0, 1, 2, 3, 4, 5, 6, 7} \draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {\ytext}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A') at (1,3) {A^{\prime}}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A) at (2,1) {A}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B') at (5,6) {B^{\prime}}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B) at (6,4) {B}; \begin{scope}[thick,>=stealth,darkred] % p: \draw (A) edge[->] (3,1); \draw (2.6,1) node[anchor=north] {p}; \draw (3,1) edge[->] (3,2); \draw (3,2) edge[->] (4,2); \draw (4,2) edge[->] (4,3); \draw (4,3) edge[->] (4,4); \draw (4,4) edge[->] (4,5); \draw (4,5) edge[->] (5,5); \draw (5,5) edge[->] (B'); \draw (5,5.4) node[anchor=east] {p}; \end{scope} \begin{scope}[thick,>=stealth,dbluecolor] % p^{\prime}: \draw (A') edge[->] (2,3); \draw (1.6,3) node[anchor=north] {p^{\prime}}; \draw (2,3) edge[->] (2,4); \draw (2,4) edge[->] (3,4); \draw (3,4) edge[->] (4,4); \draw (4,4) edge[->] (5,4); \draw (5,4) edge[->] (B); \draw (5.4,4) node[anchor=north] {p^{\prime}}; \end{scope} \end{tikzpicture}$
\end{figure}

% Fig. 2:
\begin{figure}[t]
$\begin{tikzpicture} \draw[densely dotted] (0,0) grid (7.2,7.2); % axes: \draw[->] (0,0) -- (0,7.2); \draw[->] (0,0) -- (7.2,0); \foreach \x/\xtext in {0, 1, 2, 3, 4, 5, 6, 7} \draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {\xtext}; \foreach \y/\ytext in {0, 1, 2, 3, 4, 5, 6, 7} \draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {\ytext}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A3) at (2,3) {A_3}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A2) at (3,1) {A_2}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A1) at (5,1) {A_1}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B3) at (4,6) {B_3}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B2) at (5,6) {B_2}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B1) at (6,4) {B_1}; \begin{scope}[thick,>=stealth,darkred] % p_3: \draw (A3) edge[->] (2,4); \draw (2,4) edge[->] (3,4); \draw (3,4) edge[->] (3,5); \draw (3,5) edge[->] (4,5); \draw (4,5) edge[->] (B3); \end{scope} \begin{scope}[thick,>=stealth,dbluecolor] % p_2: \draw (A2) edge[->] (4,1); \draw (4,1) edge[->] (4,2); \draw (4,2) edge[->] (4,3); \draw (4,3) edge[->] (4,4); \draw (4,4) edge[->] (5,4); \draw (5,4) edge[->] (5,5); \draw (5,5) edge[->] (B2); \end{scope} \begin{scope}[thick,>=stealth,dgreencolor] % p_1: \draw (A1) edge[->] (5,2); \draw (5,2) edge[->] (6,2); \draw (6,2) edge[->] (6,3); \draw (6,3) edge[->] (B1); \end{scope} \end{tikzpicture}$
\end{figure}

% Fig. 3:
\begin{figure}[t]
$\begin{tikzpicture} \draw[densely dotted] (-1.2,-1.2) grid (8.2,8.2); \draw (1,-1.2) -- (1,8.2); \draw (1,4.3) node[anchor=east] {x = \operatorname{x}(A')}; \draw (-1.2,1) -- (8.2,1); \draw (4,1) node[anchor=north] {y = \operatorname{y}(A)}; \draw (6,-1.2) -- (6,8.2); \draw (6,2.7) node[anchor=west] {x = \operatorname{x}(B)}; \draw (-1.2,6) -- (8.2,6); \draw (3,6) node[anchor=south] {y = \operatorname{y}(B')}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A') at (1,3) {A^{\prime}}; \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] (A) at (2,1) {A}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B') at (5,6) {B^{\prime}}; \node[circle,fill=white,draw=black,text=black,inner sep=1pt] (B) at (6,4) {B}; \begin{scope}[thick,>=stealth,darkred] % p: \draw (A) edge[->] (3,1); \draw (2.6,1) node[anchor=north] {p}; \draw (3,1) edge[->] (3,2); \draw (3,2) edge[->] (4,2); \draw (4,2) edge[->] (4,3); \draw (4,3) edge[->] (4,4); \draw (4,4) edge[->] (4,5); \draw (4,5) edge[->] (5,5); \draw (5,5) edge[->] (B'); \draw (5,5.4) node[anchor=east] {p}; \end{scope} \begin{scope}[thick,>=stealth,dashed,darkred] % \widetilde{p}: \draw (2,0) edge[->] (A); \draw (2,-1) edge[->] (2,0); \draw (2,-1.2) edge[->] (2,-1); \draw (2,-0.3) node[anchor=west] {\widetilde{p}}; \draw (B') edge[->] (5,7); \draw (5,7) edge[->] (5,8); \draw (5,8) edge (5,8.2); \draw (5,7.3) node[anchor=west] {\widetilde{p}}; \end{scope} \begin{scope}[thick,>=stealth,dbluecolor] % p^{\prime}: \draw (A') edge[->] (2,3); \draw (1.6,3) node[anchor=north] {p^{\prime}}; \draw (2,3) edge[->] (2,4); \draw (2,4) edge[->] (3,4); \draw (3,4) edge[->] (4,4); \draw (4,4) edge[->] (5,4); \draw (5,4) edge[->] (B); \draw (5.4,4) node[anchor=north] {p^{\prime}}; \end{scope} \begin{scope}[thick,>=stealth,dashed,dbluecolor] % \widetilde{p^{\prime}}: \draw (0,3) edge[->] (A'); \draw (-1,3) edge[->] (0,3); \draw (-1.2,3) edge[->] (-1,3); \draw (-0.3,3) node[anchor=north] {\widetilde{p^{\prime}}}; \draw (B) edge[->] (7,4); \draw (7,4) edge[->] (8,4); \draw (8,4) edge (8.2,4); \draw (7.3,4) node[anchor=south] {\widetilde{p^{\prime}}}; \end{scope} \end{tikzpicture}$
\end{figure}

\end{document}