LindströmGesselViennot

The LindströmGesselViennot lemma is a combinatorial result that relates the number of non-intersecting paths in a directed acyclic graph to the determinant of a matrix derived from the graph. Specifically, it applies to a set of vertices and a set of pairs of vertices, where each pair represents a desired path from a starting vertex to an ending vertex. The lemma states that the number of collections of non-intersecting paths connecting these pairs is equal to the determinant of a matrix where the entry at row i and column j is the number of paths from the i-th starting vertex to the j-th ending vertex.

This lemma has significant applications in various fields, including combinatorics, probability, and theoretical physics. It provides a powerful tool for counting problems involving configurations of non-intersecting objects. For instance, it can be used to enumerate configurations of non-intersecting random walks, which appear in statistical mechanics models. The lemma's connection to determinants also links combinatorial counting to linear algebra, offering alternative approaches to solving complex enumeration problems.

The proof of the LindströmGesselViennot lemma often involves a technique called the "sign-reversing involution," which establishes a bijection between certain sets of paths. The lemma is particularly useful when dealing with grid graphs or graphs with a specific structure, where the matrix entries can be computed more easily. Its generality and elegance make it a fundamental result in the study of enumeration and combinatorial identities.