Thursday, June 24, 2004

Lindstrom's Lemma

I recently came across an interesting combinatorial lemma on graphs. Let G be a planar DAG, and designate the 2n boundary nodes as sources and sinks (consecutively, so walking around the boundary you see first the n sources and then the n sinks). Construct the n X n matrix M where mij = number of distinct paths from source i to sink j. Then

Lindstrom's Lemma:
Each minor DI,J of M is the number of families of non-intersecting paths from sources indexed by I to sources indexed by J.

Thus, every minor of M is non-negative. A matrix having this property is said to be totally non-negative.


Source: Combinatorics and Graph Theory, by Mark Skandera
Post a Comment

Disqus for The Geomblog