In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph.
It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.
The lemma is named after Bernt Lindström, Ira Gessel and Gérard Viennot.
Let G be a locally finite directed acyclic graph.
This means that each vertex has finite degree, and that G contains no directed cycles.
This is well-defined if between any two points there are only finitely many paths; but even in the general case, this can be well-defined under some circumstances (such as all edge weights being pairwise distinct formal indeterminates, and
If one assigns the weight 1 to each edge, then e(a,b) counts the number of paths from a to b.
The Lindström–Gessel–Viennot lemma then states that the determinant of M is the signed sum over all n-tuples P = (P1, ..., Pn) of non-intersecting paths from A to B: That is, the determinant of M counts the weights of all n-tuples of non-intersecting paths starting at A and ending at B, each affected with the sign of the corresponding permutation of
In particular, if the only permutation possible is the identity (i.e., every n-tuple of non-intersecting paths from A to B takes ai to bi for each i) and we take the weights to be 1, then det(M) is exactly the number of non-intersecting n-tuples of paths starting at A and ending at B.
This n-path will be called non-intersecting just in case the paths Pi and Pj have no two vertices in common (including endpoints) whenever
Recalling the definition of M, we can expand det M as a signed sum of permutations; thus we obtain It remains to show that the sum of
denote the set of entangled twisted n-paths.
We call a vertex crowded if it belongs to at least two of the paths
The fact that the graph is acyclic implies that this is equivalent to "appearing at least twice in all the paths".
It remains to demonstrate the desired antisymmetry properties: From the construction one can see that
Thus we have found an involution with the desired properties and completed the proof of the Lindström–Gessel–Viennot lemma.
Arguments similar to the one above appear in several sources, with variations regarding the choice of which tails to switch.
A version with j smallest (unequal to i) rather than largest appears in the Gessel-Viennot 1989 reference (proof of Theorem 1).
The Lindström–Gessel–Viennot lemma can be used to prove the equivalence of the following two different definitions of Schur polynomials.
can be defined as: where the sum is over all semistandard Young tableaux T of shape λ, and the weight of a tableau T is defined as the monomial obtained by taking the product of the xi indexed by the entries i of T. For instance, the weight of the tableau
where hi are the complete homogeneous symmetric polynomials (with hi understood to be 0 if i is negative).
, which acquires the structure of a directed graph by asserting that the only allowed directions are going one to the right or one up; the weight associated to any horizontal edge at height i is xi, and the weight associated to a vertical edge is 1.
With this definition, r-tuples of paths from A to B are exactly semistandard Young tableaux of shape λ, and the weight of such an r-tuple is the corresponding summand in the first definition of the Schur polynomials.
(See also §4.5 in Sagan's book, or the First Proof of Theorem 7.16.1 in Stanley's EC2, or §3.3 in Fulmek's arXiv preprint, or §9.13 in Martin's lecture notes, for slight variations on this argument.)
One can also use the Lindström–Gessel–Viennot lemma to prove the Cauchy–Binet formula, and in particular the multiplicativity of the determinant.
The acyclicity of G is an essential assumption in the Lindström–Gessel–Viennot lemma; it guarantees (in reasonable situations) that the sums
are well-defined, and it advects into the proof (if G is not acyclic, then f might transform a self-intersection of a path into an intersection of two distinct paths, which breaks the argument that f is an involution).
Nevertheless, Kelli Talaska's 2012 paper establishes a formula generalizing the lemma to arbitrary digraphs.
are replaced by formal power series, and the sum over nonintersecting path tuples now becomes a sum over collections of nonintersecting and non-self-intersecting paths and cycles, divided by a sum over collections of nonintersecting cycles.
The reader is referred to Talaska's paper for details.