en>Tomruen: Tomruen moved page Rectified 10-cube to Rectified 10-cubes: plural content

2013-10-11T03:52:47Z

Tomruen moved page Rectified 10-cube to Rectified 10-cubes: plural content

New page

{{refimprove|date=February 2013}}

In mathematics, the '''Lindström–Gessel–Viennot lemma''' provides a way to count the number of tuples of non-intersecting lattice paths.

== Statement ==

Let ''G'' be a locally finite directed acyclic [[graph (mathematics)|graph]]. This means that each vertex has finite [[degree (graph theory)|degree]], and that ''G'' contains no directed cycles. Consider base vertices <math> A = \{ a_1, \ldots, a_n \}</math> and destination vertices <math> B = \{ b_1, \ldots, b_n \}</math>, and also assign edge weights <math>\omega_{ij}</math> for each directed edge. For each directed path ''P'' between two vertices, assign the corresponding formal product <math> \omega(P) </math> of the edges of the path. For any two vertices ''a'' and ''b'', write ''e''(''a'',''b'') as the formal sum over all paths <math>e(a,b) = \sum_{P: a \to b} \omega(P)</math>. In particular, if between any two points there are only finitely many paths, one can assign the weight 1 to each edge and then ''e''(''a'',''b'') counts the number of paths from ''a'' to ''b''.

With this setup, write
:<math> M = \begin{pmatrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n) \\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n) \\ \vdots & \vdots & \ddots & \vdots \\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \end{pmatrix} </math>.

The '''Lindström–Gessel–Viennot lemma''' then states that the determinant of ''M'' is the signed sum over all ''n''-tuples ''P'' = (''P''1, ..., ''P''''n'') of ''non-intersecting'' paths from ''A'' to ''B'':

:<math> \det(M) = \sum_{(P_1,\ldots,P_n) \colon A \to B} \mathrm{sign}(\sigma(P)) \prod_{i=1}^n \omega(P_i). </math>

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 <math>(1,2,\ldots,n)</math>, given by <math> P_i </math> taking <math> a_i </math> to <math> b_{\sigma(i)} </math>.

In particular, if we can take the weights to be 1 and the only permutation possible is the identity (i.e., every ''n''-tuple of non-intersecting paths from ''A'' to ''B'' takes ''a''''i'' to ''b''''i'' for each ''i''), then det(''M'') is exactly the number of non-intersecting ''n''-tuples of paths starting at ''A'' and ending at ''B''.

== Proof ==

To prove the Lindström–Gessel–Viennot lemma, one uses an [[involution (mathematics)|involution]], whose fixed points are precisely the tuples of nonintersecting paths, and which preserves the weights. To define this involution ''f'' on the set of all ''n''-tuples of paths from ''A'' to ''B'', we define ''f'' to fix any tuple of nonintersecting paths, and for a tuple which contains an intersection, we want to switch the tails of the paths so as to give the negative sign in the above formula. To make sure this is well defined, it is necessary to define an ordering on the paths that intersect. Let ''i'' be the smallest index such that the path starting at ''a''''i'' contains an intersection, and then let ''j'' be the largest index such that a path intersecting the previous one starts at ''a''''j''. Then define ''f'' to switch the tails of these two paths. This is a well defined involution on the set of all ''n''-tuples of paths from ''A'' to ''B'', whose fixed points is exactly the set of non-intersecting tuples.

== Applications ==

=== Schur polynomials ===

The Lindström–Gessel–Viennot lemma can be used to prove the equivalence of the following two different definitions of [[Schur polynomial]]s. Given a partition <math> \lambda = \lambda_1 + \cdots + \lambda_r </math> of ''n'', the Schur polynomial <math>s_\lambda(x_1,\ldots,x_n)</math> can be defined as:
*<math> s_\lambda(x_1,\ldots,x_n) = \sum_T w(T), </math>
where the sum is over all semistandard Young tableaux ''T'' of shape ''λ'', and the weight of a tableau is given by the corresponding monomial, obtained by taking the product of the ''x''''i'' indexed by the entries of ''T''. For instance, the weight of the tableau
[[Image:RSK example result.svg]]
is <math> x_1 x_3 x_4^3 x_5 x_6 x_7 </math>.
*<math> s_\lambda(x_1, \ldots, x_n) = \det \left ( (h_{\lambda_i +j-i} )_{i,j}^{r \times r} \right ), </math>
where ''h''''i'' are the [[complete homogeneous symmetric polynomial]]s. For instance, for the partition (3,2,2,1), the corresponding determinant is
:<math> D = \begin{vmatrix} h_3 & h_4 & h_5 & h_6 \\ h_1 & h_2 & h_3 & h_4 \\ 1 & h_1 & h_2 & h_3 \\ 0 & 0 & 1 & h_1 \end{vmatrix}.</math>

To prove the equivalence, given any partition ''λ'' as above, one considers the ''r'' starting points <math> a_i = (r+1-i,1) </math> and the ''r'' ending points <math> b_i = (\lambda_i + r+1-i, n)</math>, as points in the lattice <math> \mathbb{Z}^2 </math>, 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 ''x''''i'', 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. For instance, with the tableau
[[Image:RSK example result.svg]],
one gets the corresponding ''4''-tuple

[[Image:Schur lattice paths.svg]]

On the other hand, the matrix ''M'' is exactly the matrix written above for ''D''. This shows the required equivalence.

=== The Cauchy–Binet formula ===

One can also use the Lindström–Gessel–Viennot lemma to prove the [[Cauchy–Binet formula]], and in particular the multiplicativity of the determinant.

== See also ==
[[Kirchhoff's theorem|Matrix tree theorem]]

[[Cauchy–Binet formula]]

==References==
* [[Bruce Sagan|Bruce E. Sagan]]. ''The [[symmetric group|Symmetric Group]]''. Springer, 2001.

{{DEFAULTSORT:Lindstrom-Gessel-Viennot lemma}}
[[Category:Lemmas]]
[[Category:Combinatorics]]
[[Category:Theorems in combinatorics]]

Rectified 10-cubes - Revision history

en>Tomruen: Tomruen moved page Rectified 10-cube to Rectified 10-cubes: plural content