ukmuiik

Question

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
$mathbbZ^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 $mathbbZ^2$), and whose
arcs are
beginalign*
left( i,jright) & rightarrowleft( i,j+1right) qquadtextfor all
left( i,jright) inmathbbZ^2 text, qquad textand\
left( i,jright) & rightarrowleft( i+1,jright) qquadtextfor all
left( i,jright) inmathbbZ^2 text.
endalign*
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,jright) $, we set $operatorname*xleft(
vright) =i$ and $operatorname*yleft( vright) =j$. We refer to
$operatorname*xleft( vright) $ as the x-coordinate of $v$, and
to $operatorname*yleft( vright) $ 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
beginalign*
operatorname*xleft( A^primeright) & leqoperatorname*xleft(
Aright) ,qquadoperatorname*yleft( A^primeright) geq
operatorname*yleft( Aright) ,\
operatorname*xleft( B^primeright) & leqoperatorname*xleft(
Bright) ,qquadoperatorname*yleft( B^primeright) geq
operatorname*yleft( Bright) .
endalign*
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.

Non-intersecting lattice paths and Proposition 2

Now, fix a nonnegative integer $k$. Let $left[ kright] $ be the set
$left 1,2,ldots,kright $. Let $mathfrakS_k$ be the group of all
permutations of $left[ kright] $.

A $k$-vertex shall mean a $k$-tuple of vertices. If $mathbfv
=left( A_1,A_2,ldots,A_kright) $ is a $k$-vertex, and if $sigma
inmathfrakS_k$, then $sigmaleft( mathbfvright) $ denotes the
$k$-vertex $left( A_sigmaleft( 1right) ,A_sigmaleft( 2right)
,ldots,A_sigmaleft( kright) right) $.

If $left( A_1,A_2,ldots,A_kright) $ and $left( B_1,B_2
,ldots,B_kright) $ are two $k$-vertices, then a NILP from
$left( A_1,A_2,ldots,A_kright) $ to $left( B_1,B_2
,ldots,B_kright) $ shall mean a $k$-tuple $left( p_1,p_2
,ldots,p_kright) $ 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.)

If $mathbfu$ and $mathbfv$ are two $k$-vertices, then $Nleft(
mathbfu,mathbfvright) $ denotes the set of all NILPs from $mathbfu$
to $mathbfv$.

A pair $left( mathbfu,mathbfvright) $ of two $k$-vertices
$mathbfu$ and $mathbfv$ is said to be nonpermutable if and only
if every $sigmainmathfrakS_k$ satisfying $sigmaneqoperatorname*id$
satisfies $Nleft( mathbfu,sigmaleft( mathbfvright) right)
=varnothing$. Note that we are not requiring that $Nleft( mathbfu
,mathbfvright) neqvarnothing$ here.

Proposition 2. Let $mathbfu=left( A_1,A_2,ldots,A_kright) $
and $mathbfv=left( B_1,B_2,ldots,B_kright) $ be two $k$-vertices
such that
beginalign*
operatorname*xleft( A_1right) & geqoperatorname*xleft(
A_2right) geqcdotsgeqoperatorname*xleft( A_kright) ;\
operatorname*yleft( A_1right) & leqoperatorname*yleft(
A_2right) leqcdotsleqoperatorname*yleft( A_kright) ;\
operatorname*xleft( B_1right) & geqoperatorname*xleft(
B_2right) geqcdotsgeqoperatorname*xleft( B_kright) ;\
operatorname*yleft( B_1right) & leqoperatorname*yleft(
B_2right) leqcdotsleqoperatorname*yleft( B_kright) .
endalign*
Then, the pair $left( mathbfu,mathbfvright) $ is nonpermutable.

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_ain R$ is given.
We call this element $omega_a$ the weight of $a$. If $p$ is any path,
then we let $omegaleft( pright) $ be the product of the weights
$omega_a$ over all arcs $a$ of $p$. If $mathbfp=left( p_1
,p_2,ldots,p_kright) $ is a NILP from a $k$-vertex $mathbfu$ to a
$k$-vertex $mathbfv$, then we define the weight $omegaleft(
mathbfpright) $ of this NILP $mathbfp$ to be the product $prod
_i=1^komegaleft( p_iright) $.

If $A$ and $B$ are two vertices, then $Nleft( A,Bright) $ 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 $mathbfu=left( A_1,A_2,ldots,A_kright) $ and
$mathbfv=left( B_1,B_2,ldots,B_kright) $ be two $k$-vertices.
Then,
beginalign*
detleft( left( sum_pin Nleft( A_i,B_jright) omegaleft(
pright) right) _1leq ileq k, 1leq jleq kright)
& =sum_sigmainmathfrakS_kleft( -1right) ^sigmasum
_mathbfpin Nleft( mathbfu,sigmaleft( mathbfvright) right)
omegaleft( mathbfpright) .
endalign*
(Here, $left( -1right) ^sigma$ denotes the sign of the permutation
$sigma$.)

If a pair $left( mathbfu,mathbfvright) $ 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 $mathbfu=left( A_1,A_2,ldots,A_kright) $
and $mathbfv=left( B_1,B_2,ldots,B_kright) $ be two $k$-vertices
such that
beginalign*
operatorname*xleft( A_1right) & geqoperatorname*xleft(
A_2right) geqcdotsgeqoperatorname*xleft( A_kright) ;\
operatorname*yleft( A_1right) & leqoperatorname*yleft(
A_2right) leqcdotsleqoperatorname*yleft( A_kright) ;\
operatorname*xleft( B_1right) & geqoperatorname*xleft(
B_2right) geqcdotsgeqoperatorname*xleft( B_kright) ;\
operatorname*yleft( B_1right) & leqoperatorname*yleft(
B_2right) leqcdotsleqoperatorname*yleft( B_kright) .
endalign*
Then,
beginalign*
detleft( left( sum_pin Nleft( A_i,B_jright) omegaleft(
pright) right) _1leq ileq k, 1leq jleq kright) =sum
_mathbfpin Nleft( mathbfu,mathbfvright) omegaleft(
mathbfpright) .
endalign*

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.

Any pictures illustrating the facts are highly welcome -- e.g., the definition of a lattice path, that of a NILP, the situation of Lemma 1, and that of Proposition 2. — Aug 3 at 1:34

score 1 · Answer 1 · 2018-08-03 12:05:14Z

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 $ellleft( qright) $ of $q$ is
defined to be the number of arcs of $q$.

We shall now prove Lemma 1 by strong induction on $ellleft( pright)
+ellleft( p^primeright) $:

Induction step: Fix a nonnegative integer $N$. Assume (as the induction
hypothesis) that Lemma 1 holds whenever $ellleft( pright) +ellleft(
p^primeright) <N$. We must now prove that Lemma 1 holds when $ellleft(
pright) +ellleft( p^primeright) =N$.

So let $A$, $B$, $A^prime$, $B^prime$, $p$ and $p^prime$ be as in
Lemma 1, and let us assume that $ellleft( pright) +ellleft( 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*xleft( Aright)
leqoperatorname*xleft( B^primeright) $ and $operatorname*y
left( Aright) leqoperatorname*yleft( B^primeright) $.
Similarly, the existence of a path $p^prime$ from $A^prime$ to $B$
yields $operatorname*xleft( A^primeright) leqoperatorname*x
left( Bright) $ and $operatorname*yleft( A^primeright)
leqoperatorname*yleft( Bright) $.

Next, we claim that $ellleft( pright) neq0$.

[Proof: Assume the contrary. Thus, $ellleft( pright) =0$. Hence,
the path $p$ has no steps. Therefore, $A=B^prime$ (since $p$ is a path from
$A$ to $B^prime$). Hence, $operatorname*yleft( Aright)
=operatorname*yleft( B^primeright) geqoperatorname*yleft(
Bright) $, so that $operatorname*yleft( A^primeright)
geqoperatorname*yleft( Aright) geqoperatorname*yleft( Bright)
$. Combining this with $operatorname*yleft( A^primeright)
leqoperatorname*yleft( Bright) $, we obtain $operatorname*yleft(
A^primeright) =operatorname*yleft( Bright) $. Combining
$operatorname*yleft( A^primeright) geqoperatorname*yleft(
Aright) $ with $operatorname*yleft( A^primeright)
=operatorname*yleft( Bright) leqoperatorname*yleft( Aright) $,
we obtain $operatorname*yleft( A^primeright) =operatorname*y
left( Aright) $. Thus, $operatorname*yleft( Aright)
=operatorname*yleft( A^primeright) =operatorname*yleft( Bright) $.
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*xleft(
A^primeright) leqoperatorname*xleft( underbraceA_=B^prime
right) =operatorname*xleft( B^primeright) leqoperatorname*x
left( Bright) $).

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*yleft( A^primeright) <operatorname*y
left( Bright) $ (since $p^prime$ is a path from $A^prime$ to $B$).
But this would contradict $operatorname*yleft( A^primeright)
geqoperatorname*yleft( Bright) $. 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, $ellleft( pright) neq0$ is proven.]

Furthermore, we claim that $ellleft( p^primeright) neq0$.

[Proof: Assume the contrary. Thus, $ellleft( p^primeright)
=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*xleft( A^primeright) =operatorname*xleft(
Bright) geqoperatorname*xleft( B^primeright) $, so that
$operatorname*xleft( Aright) geqoperatorname*xleft( A^prime
right) geqoperatorname*xleft( B^primeright) $. Combining this
with $operatorname*xleft( Aright) leqoperatorname*xleft(
B^primeright) $, we obtain $operatorname*xleft( Aright)
=operatorname*xleft( B^primeright) $. Combining $operatorname*x
left( Aright) geqoperatorname*xleft( A^primeright) $ with
$operatorname*xleft( A^primeright) geqoperatorname*xleft(
B^primeright) =operatorname*xleft( Aright) $, we obtain
$operatorname*xleft( Aright) =operatorname*xleft( A^prime
right) $. Thus, $operatorname*xleft( A^primeright)
=operatorname*xleft( Aright) =operatorname*xleft( 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^primeright) geqoperatorname*yleft( Aright) $ and
$operatorname*yleft( underbraceA^prime_=Bright)
=operatorname*yleft( Bright) leqoperatorname*yleft( 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*xleft( Aright) <operatorname*xleft( B^prime
right) $ (since $p$ is a path from $A$ to $B^prime$). But this would
contradict $operatorname*xleft( Aright) =operatorname*xleft(
B^primeright) $. 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,
$ellleft( p^primeright) neq0$ is proven.]

Let $P$ be the second vertex of the path $p$. (This is well-defined, since
$ellleft( pright) neq0$.) Hence, $P$ lies on a path from $A$ to
$B^prime$ (namely, on the path $p$). Therefore, $operatorname*xleft(
Aright) leqoperatorname*xleft( Pright) leqoperatorname*xleft(
B^primeright) $ (since the x-coordinates of the vertices a path are
always weakly increasing) and $operatorname*yleft( Aright)
leqoperatorname*yleft( Pright) leqoperatorname*yleft( 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, $ellleft( rright) =ellleft( pright)
-1<ellleft( pright) $ and thus $underbraceellleft( rright)
_<ellleft( pright) +ellleft( p^primeright) <ellleft(
pright) +ellleft( p^primeright) =N$.

Moreover, $operatorname*xleft( A^primeright) leqoperatorname*x
left( Aright) leqoperatorname*xleft( Pright) $. If we had
$operatorname*yleft( A^primeright) geqoperatorname*yleft(
Pright) $, then we could apply Lemma 1 to $P$ and $r$ instead of $A$ and $p$
(by the induction hypothesis, since $ellleft( rright) +ellleft(
p^primeright) <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*yleft( A^primeright) geqoperatorname*yleft(
Pright) $. Thus, $operatorname*yleft( A^primeright)
<operatorname*yleft( Pright) $. Hence, $operatorname*yleft(
A^primeright) leqoperatorname*yleft( Pright) -1$ (since
$operatorname*yleft( A^primeright) $ and $operatorname*yleft(
Pright) $ 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*yleft( Pright) =operatorname*yleft( Aright) $,
which would contradict $operatorname*yleft( Aright) leq
operatorname*yleft( A^primeright) <operatorname*yleft(
Pright) $. Hence, this arc cannot be an east-step. Thus, this arc must be a
north-step. Therefore, $operatorname*yleft( Pright) =operatorname*y
left( Aright) +1$ and $operatorname*xleft( Pright)
=operatorname*xleft( Aright) $. Combining $operatorname*yleft(
A^primeright) leqoperatorname*yleft( Pright) -1=operatorname*y
left( Aright) $ (since $operatorname*yleft( Pright)
=operatorname*yleft( Aright) +1$) with $operatorname*yleft(
A^primeright) geqoperatorname*yleft( Aright) $, we obtain
$operatorname*yleft( A^primeright) =operatorname*yleft(
Aright) $.

Let $P^prime$ be the second vertex on the path $p^prime$. (This is
well-defined, since $ellleft( p^primeright) neq0$.) Hence,
$P^prime$ lies on a path from $A^prime$ to $B$ (namely, on the path
$p^prime$). Therefore, $operatorname*xleft( A^primeright)
leqoperatorname*xleft( P^primeright) leqoperatorname*xleft(
Bright) $ (since the x-coordinates of the vertices a path are always weakly
increasing) and $operatorname*yleft( A^primeright) leq
operatorname*yleft( P^primeright) leqoperatorname*yleft(
Bright) $ (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, $ellleft(
r^primeright) =ellleft( p^primeright) -1<ellleft( p^prime
right) $ and thus $ellleft( pright) +underbraceellleft(
r^primeright) _<ellleft( p^primeright) <ellleft( pright)
+ellleft( p^primeright) =N$.

Moreover, $operatorname*yleft( P^primeright) geqoperatorname*y
left( A^primeright) geqoperatorname*yleft( Aright) $. If we had
$operatorname*xleft( P^primeright) leqoperatorname*xleft(
Aright) $, then we could apply Lemma 1 to $P^prime$ and $r^prime$
instead of $A^prime$ and $p^prime$ (by the induction hypothesis, since
$ellleft( pright) +ellleft( r^primeright) <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*xleft( P^primeright)
leqoperatorname*xleft( Aright) $. Thus, $operatorname*xleft(
P^primeright) >operatorname*xleft( Aright) $. Hence,
$operatorname*xleft( P^primeright) geqoperatorname*xleft(
Aright) +1$ (since $operatorname*xleft( P^primeright) $ and
$operatorname*xleft( Aright) $ 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*xleft( P^primeright)
=operatorname*xleft( A^primeright) $, which would contradict
$operatorname*xleft( A^primeright) leqoperatorname*xleft(
Aright) <operatorname*xleft( P^primeright) $. Hence, this arc
cannot be a north-step. Thus, this arc must be an east-step. Therefore,
$operatorname*yleft( P^primeright) =operatorname*yleft(
A^primeright) $ and $operatorname*xleft( P^primeright)
=operatorname*xleft( A^primeright) +1$. Hence, $operatorname*x
left( A^primeright) +1=operatorname*xleft( P^primeright)
geqoperatorname*xleft( Aright) +1$, so that $operatorname*xleft(
A^primeright) geqoperatorname*xleft( Aright) $. Combining this
with $operatorname*xleft( A^primeright) leqoperatorname*xleft(
Aright) $, we obtain $operatorname*xleft( A^primeright)
=operatorname*xleft( Aright) $.

Now, the vertices $A$ and $A^prime$ have the same x-coordinate (since
$operatorname*xleft( A^primeright) =operatorname*xleft(
Aright) $) and the same y-coordinate (since $operatorname*yleft(
A^primeright) =operatorname*yleft( Aright) $). 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 $ellleft( pright)
+ellleft( p^primeright) =N$, then $p$ and $p^prime$ have a vertex
in common. In other words, Lemma 1 holds when $ellleft( pright)
+ellleft( p^primeright) =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*xleft( Aright) leqoperatorname*xleft( B^prime
right) $ and $operatorname*yleft( Aright) leqoperatorname*y
left( B^primeright) $. Similarly, the existence of $p^prime$ yields
$operatorname*xleft( A^primeright) leqoperatorname*xleft(
Bright) $ and $operatorname*yleft( A^primeright) leq
operatorname*yleft( Bright) $.

Thus,
beginalign*
operatorname*xleft( A^primeright) & leqoperatorname*xleft(
Aright) leqoperatorname*xleft( B^primeright) leq
operatorname*xleft( Bright) qquadtextand\
operatorname*yleft( Aright) & leqoperatorname*yleft( A^prime
right) leqoperatorname*yleft( Bright) leqoperatorname*yleft(
B^primeright) .
endalign*
Now, consider the rectangle whose four sides are given by the equations
beginalign*
x=operatorname*xleft( A^primeright) ,qquad y=operatorname*y
left( Aright) ,qquad x=operatorname*xleft( Bright) ,qquad
y=operatorname*yleft( B^primeright) ,
endalign*
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*xleft(
A^primeright) leqoperatorname*xleft( Aright) leq
operatorname*xleft( B^primeright) leqoperatorname*xleft(
Bright) $ and $operatorname*yleft( Aright) leqoperatorname*y
left( A^primeright) leqoperatorname*yleft( Bright)
leqoperatorname*yleft( B^primeright) $). 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).

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 $widetildep$ by
vertical steps (i.e., arcs of the form $left( i,jright) rightarrowleft(
i,j+1right) $) in both directions (so the path $widetildep$ 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). We
extend the path $p^prime$ to a bidirectionally infinite path
$widetildep^prime$ by horizontal steps (i.e., arcs of the form $left(
i,jright) rightarrowleft( i+1,jright) $) in both directions. The
resulting infinite paths $widetildep$ and $widetildep^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 $widetildep$ and
$widetildep^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*xleft(
Cright) +operatorname*yleft( Cright) $ is incremented by $1$ with
each step. Hence, if $q$ is a bidirectionally infinite path, then, for each
$NinmathbbZ$, there is a unique vertex $C$ of $q$ satisfying
$operatorname*xleft( Cright) +operatorname*yleft( Cright) =N$.
Denote this vertex $C$ by $h_Nleft( qright) $. Thus, the vertices of $q$
are $ldots,h_-1left( qright) ,h_0left( qright) ,h_1left(
qright) ,ldots$ in this order.

All sufficiently low $NinmathbbZ$ satisfy $operatorname*xleft(
h_Nleft( widetildep^primeright) right) <operatorname*xleft(
h_Nleft( widetildepright) right) $, whereas all sufficiently high
$NinmathbbZ$ satisfy $operatorname*xleft( h_Nleft(
widetildep^primeright) right) >operatorname*xleft( h_Nleft(
widetildepright) right) $. Hence, the set of all $NinmathbbZ$ that
satisfy $operatorname*xleft( h_Nleft( widetildep^primeright)
right) <operatorname*xleft( h_Nleft( widetildepright) right)
$ is a nonempty set of integers that is bounded from above. Therefore, this
set has a maximum. Let $M$ be this maximum. Thus, $MinmathbbZ$ satisfies
$operatorname*xleft( h_Mleft( widetildep^primeright) right)
<operatorname*xleft( h_Mleft( widetildepright) right) $ but
$operatorname*xleft( h_M+1left( widetildep^primeright)
right) geqoperatorname*xleft( h_M+1left( widetildepright)
right) $.

But the point $h_M+1left( widetildep^primeright) $ is either the
eastern or the northern neighbor of $h_Mleft( widetildep^prime
right) $; hence, $operatorname*xleft( h_M+1left(
widetildep^primeright) right) leqoperatorname*xleft(
h_Mleft( widetildep^primeright) right) +1$. Also, the point
$h_M+1left( widetildepright) $ is either the eastern or the northern
neighbor of $h_Mleft( widetildepright) $; thus, $operatorname*x
left( h_M+1left( widetildepright) right) geqoperatorname*x
left( h_Mleft( widetildepright) right) $. Hence,
beginalign*
operatorname*xleft( h_M+1left( widetildep^primeright)
right) lequnderbraceoperatorname*xleft( h_Mleft(
widetildep^primeright) right) _<operatorname*xleft(
h_Mleft( widetildepright) right) +1<underbraceoperatorname*x
left( h_Mleft( widetildepright) right) _leqoperatorname*x
left( h_M+1left( widetildepright) right) +1leqoperatorname*x
left( h_M+1left( widetildepright) right) +1.
endalign*
Therefore, $operatorname*xleft( h_M+1left( widetildep^prime
right) right) leqoperatorname*xleft( h_M+1left( widetildep
right) right) $ (since both sides are integers). Combining this with
$operatorname*xleft( h_M+1left( widetildep^primeright)
right) geqoperatorname*xleft( h_M+1left( widetildepright)
right) $, we obtain $operatorname*xleft( h_M+1left(
widetildep^primeright) right) =operatorname*xleft(
h_M+1left( widetildepright) right) $. Hence, $h_M+1left(
widetildep^primeright) =h_M+1left( widetildepright) $ (since
$operatorname*xleft( h_M+1left( widetildep^primeright)
right) -operatorname*yleft( h_M+1left( widetildep^prime
right) right) =M+1=operatorname*xleft( h_M+1left( widetildep
right) right) -operatorname*yleft( h_M+1left( widetildep
right) right) $ as well). Thus, the paths $widetildep$ and
$widetildep^prime$ have a vertex in common (namely, $h_M+1left(
widetildep^primeright) =h_M+1left( widetildepright) $). 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 $sigmainmathfrakS_k$ be such that
$sigmaneqoperatorname*id$. We shall show that $Nleft( mathbfu
,sigmaleft( mathbfvright) right) =varnothing$. Indeed, let
$mathbfpin Nleft( mathbfu,sigmaleft( mathbfvright) right) $.

The permutation $sigma$ has at least one inversion (since $sigma
neqoperatorname*id$). In other words, there exist two elements $i$ and $j$
of $left[ kright] $ such that $i<j$ and $sigmaleft( iright)
>sigmaleft( jright) $. Consider such $i$ and $j$.

Write $mathbfp$ in the form $mathbfp=left( p_1,p_2,ldots
,p_kright) $. Thus, $left( p_1,p_2,ldots,p_kright) $ is a NILP
from $mathbfu$ to $sigmaleft( mathbfvright) $ (since $left(
p_1,p_2,ldots,p_kright) =mathbfpin Nleft( mathbfu
,sigmaleft( mathbfvright) right) $). In other words, $left( p_1,p_2,ldots,p_kright) $ is a NILP from $left(A_1, A_2, ldots, A_kright)$ to $left(B_sigmaleft(1right), B_sigmaleft(2right), ldots, B_sigmaleft(kright)right)$ (since $mathbfu = left(A_1, A_2, ldots, A_kright)$ and $sigmaleft(mathbfvright) = sigmaleft(B_1, B_2, ldots, B_kright) = left(B_sigmaleft(1right), B_sigmaleft(2right), ldots, B_sigmaleft(kright)right)$). By the definition of a NILP,
this implies that

$p_i$ is a path from $A_i$ to $B_sigmaleft( iright) $;

$p_j$ is a path from $A_j$ to $B_sigmaleft( jright) $;

the paths $p_i$ and $p_j$ have no vertex in common (since $ineq j$).

One of the assumptions of Proposition 2 was $operatorname*xleft(
A_1right) geqoperatorname*xleft( A_2right) geqcdots
geqoperatorname*xleft( A_kright) $; hence, $operatorname*xleft(
A_iright) geqoperatorname*xleft( A_jright) $ (since $i<j$), and
thus $operatorname*xleft( A_jright) leqoperatorname*xleft(
A_iright) $. Similarly, the second assumption of Proposition 2 yields $operatorname*yleft( A_jright) geqoperatorname*yleft(
A_iright) $.
Also, the third assumption of Proposition 2 says $operatorname*xleft( B_1right) geqoperatorname*xleft(
B_2right) geqcdotsgeqoperatorname*xleft( B_kright)$; hence,
$operatorname*xleft( B_sigmaleft( jright)
right) geqoperatorname*xleft( B_sigmaleft( iright) right) $ (since $sigmaleft( jright) <sigmaleft( iright) $),
so that
$operatorname*xleft( B_sigmaleft( iright)
right) leqoperatorname*xleft( B_sigmaleft( jright) right) $.
Similarly, the fourth assumption of Proposition 2 yields $operatorname*yleft( B_sigmaleft( iright) right)
geqoperatorname*yleft( B_sigmaleft( jright) right) $. Hence,
Lemma 1 (applied to $A=A_i$, $B=B_sigmaleft( jright) $, $A^prime
=A_j$, $B^prime=B_sigmaleft( iright) $, $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 $mathbfp$. Thus, we have found a contradiction
for each $mathbfpin Nleft( mathbfu,sigmaleft( mathbfvright)
right) $. Hence, there exists no $mathbfpin Nleft( mathbfu
,sigmaleft( mathbfvright) right) $. In other words, $Nleft(
mathbfu,sigmaleft( mathbfvright) right) =varnothing$.

Now, forget that we fixed $sigma$. Thus, we have shown that every $sigma
inmathfrakS_k$ satisfying $sigmaneqoperatorname*id$ satisfies
$Nleft( mathbfu,sigmaleft( mathbfvright) right) =varnothing$.
In other words, the pair $left( mathbfu,mathbfvright) $ 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(
mathbfu,mathbfvright) $ is nonpermutable. In other words, every
$sigmainmathfrakS_k$ satisfying $sigmaneqoperatorname*id$
satisfies $Nleft( mathbfu,sigmaleft( mathbfvright) right)
=varnothing$. Hence, every $sigmainmathfrakS_k$ satisfying $sigma
neqoperatorname*id$ satisfies
beginalign*
sum_mathbfpin Nleft( mathbfu,sigmaleft( mathbfvright)
right) omegaleft( mathbfpright) =sum_mathbfpinvarnothing
omegaleft( mathbfpright) =left( textempty sumright) =0.
label1 tag1
endalign*
But Theorem 3 yields
beginalign*
& detleft( left( sum_pin Nleft( A_i,B_jright) omegaleft(
pright) right) _1leq ileq k, 1leq jleq kright) \
& =sum_sigmainmathfrakS_kleft( -1right) ^sigma
sum_mathbfpin Nleft( mathbfu,sigmaleft( mathbfvright)
right) omegaleft( mathbfpright) \
& =underbraceleft( -1right) ^operatorname*id_=1underbracesum
_mathbfpin Nleft( mathbfu,operatorname*idleft( mathbfv
right) right) _substack=sum_mathbfpin Nleft( mathbfu
,mathbfvright) \text(since operatorname*idleft( mathbfv
right) =mathbfvtext)omegaleft( mathbfpright) +sum
_substacksigmainmathfrakS_k;\sigmaneqoperatorname*idleft(
-1right) ^sigmaunderbracesum_mathbfpin Nleft( mathbfu
,sigmaleft( mathbfvright) right) omegaleft( mathbfpright)
_substack=0\text(by eqref1, since sigmaneqoperatorname*idtext)\
& qquad left( texthere, we have split off the addend for sigma = operatornameid text from the sum right) \
& =sum_mathbfpin Nleft( mathbfu,mathbfvright) omegaleft(
mathbfpright) +underbracesum_substacksigmainmathfrakS
_k;\sigmaneqoperatorname*idleft( -1right) ^sigma0_=0
=sum_mathbfpin Nleft( mathbfu,mathbfvright) omegaleft(
mathbfpright) .
endalign*
This proves Corollary 4.

score 1 · Answer 2 · 2018-08-03 12:05:14Z