Lindström Nonintersecting Paths
Cancel intersecting path families with a determinant and retain signed disjoint witnesses.
Free theory articleCancel intersecting path families with a determinant and retain signed disjoint witnesses.
Concept & interpretation
The Lindström-Gessel-Viennot lemma provides a way to count the number of disjoint (non-intersecting) path families in a directed acyclic graph.
Experiment
In this interactive module, you can explore the Lindström-Gessel-Viennot lemma in a grid-like directed acyclic graph where paths can only move right and up.
- Use the Terminals control to change the configuration of the sink nodes. You can select "Swapped sinks" to reverse the roles of identity and swapped path families, or "Shared sink" which naturally collapses the Determinant to zero.
- Use the Obstacle control and select "Center" to place a block in the center of the grid, limiting the available paths and reducing the total disjoint families.
- Compare the resulting Determinant and Signed family count observable results.