Lema de Lindström-Gessel-Viennot

En matemáticas, el lema de Lindström-Gessel-Viennot proporciona una manera de contar las tuplas de un conjunto de caminos reticulares no intersecantes o, de forma más general, caminos en un grafo dirigido. Fue demostrado por Gessel-Viennot en 1985, basándose en trabajos previos de Lindström publicados en 1973. El lema recibe su nombre de Bernt Lindström, Ira Gessel y Gérard Viennot.

Fue Bernt Lindtröm quien en 1972 formuló y demostró el lema en el contexto de los matroides, pero no se publicó en aquel momento. En 1985, fue reformulado y demostrado por Ira Gessel y Gérard Viennot en el contexto de los grafos. Ambos demostraron su versatilidad y lo popularizaron instantáneamente.^[1]​

Sea G un grafo acíclico dirigido localmente finito. Esto significa que cada vértice tiene grado finito y que G no contiene ciclos dirigidos. Considérense los vértices base ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ y los vértices de destino ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$, y asígnese también un peso ${\displaystyle \omega _{e}}$ a cada arista dirigida e. Se supone que estos pesos de arista pertenecen a algún anillo conmutativo. Para cada camino dirigido P entre dos vértices, sea ${\displaystyle \omega (P)}$ el producto de los pesos de las aristas del camino. Para dos vértices cualesquiera, a y b, escríbase e(a,b) para la suma ${\displaystyle e(a,b)=\sum _{P:a\to b}\omega (P)}$ de todos los caminos de a a b. Si se asigna el peso 1 a cada arista, entonces e(a,b) es el número de caminos de a a b.

Con esta configuración, escríbase

${\displaystyle 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}}}$.

Una n-tupla de caminos no intersecantes de A a B significa una n-tupla (P₁, ..., P_n) de caminos en G con las siguientes propiedades:

• Existe una permutación ${\displaystyle \sigma }$ de ${\displaystyle \left\{1,2,...,n\right\}}$ tal que, para cada i, el camino P_i es un camino de ${\displaystyle a_{i}}$ a ${\displaystyle b_{\sigma (i)}}$.
• Siempre que ${\displaystyle i\neq j}$, las rutas P_i y P_j no tienen dos vértices en común (ni siquiera extremos).

Dada dicha n-tupla (P₁, ..., P_n), se denota por ${\displaystyle \sigma (P)}$ la permutación de ${\displaystyle \sigma }$ de la primera condición.

El lema de Lindström–Gessel–Viennot establece que el determinante de M es la suma con signo de todas las n-tuplas P = (P₁, ..., P_n) de caminos no intersecantes de A a B:

${\displaystyle \det(M)=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\prod _{i=1}^{n}\omega (P_{i}).}$

Es decir, el determinante de M cuenta los pesos de todas las n-tuplas de caminos no intersecantes que empiezan en A y terminan en B, cada una afectada por el signo de la permutación correspondiente de ${\displaystyle (1,2,\ldots ,n)}$, dada por ${\displaystyle P_{i}}$, que lleva de ${\displaystyle a_{i}}$ a ${\displaystyle b_{\sigma (i)}}$.

En particular, si la única permutación posible es la identidad (es decir, cada n-tupla de caminos no intersecantes de A a B toma a_i a b_i para cada i) y se toman los pesos como 1, entonces det(M) es exactamente el número de n-tuplas no intersecantes de caminos que empiezan en A y terminan en B.

Para demostrar el lema de Lindström-Gessel-Viennot, primero se introduce algo de notación.

Un n-camino desde una n-tupla ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ de vértices de G a una n-tupla ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ de vértices de G significará una n-tupla ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ de caminos en G, donde cada ${\displaystyle P_{i}}$ lleva de ${\displaystyle a_{i}}$ a ${\displaystyle b_{i}}$. Este n-camino se llamará no intersecante solo si los caminos P_i y P_j no tienen dos vértices en común (incluidos los extremos) siempre que sea ${\displaystyle i\neq j}$. De lo contrario, se llamará enredado.

Dado un n-camino ${\displaystyle P=(P_{1},P_{2},\ldots ,P_{n})}$, el peso ${\displaystyle \omega (P)}$ de este n-camino se define como el producto ${\displaystyle \omega (P_{1})\omega (P_{2})\cdots \omega (P_{n})}$.

Un n-camino retorcido desde una n-tupla ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ de vértices de G a una n-tupla ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ de vértices de G significará un n-camino de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ a ${\displaystyle \left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)}$ para alguna permutación ${\displaystyle \sigma }$ en el grupo simétrico ${\displaystyle S_{n}}$. Esta permutación ${\displaystyle \sigma }$ se denominará la torsión de este n-camino retorcido y se denotará por ${\displaystyle \sigma (P)}$ (donde P es el n-camino). Esto, por supuesto, generaliza la notación ${\displaystyle \sigma (P)}$ presentada anteriormente.

Recordando la definición de M, se puede desarrollar el determinante de M como una suma con signo de permutaciones; así se obtiene:

${\displaystyle {\begin{array}{rcl}\det M&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}e(a_{i},b_{\sigma (i)})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}\sum _{P_{i}:a_{i}\to b_{\sigma (i)}}\omega (P_{i})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\sum \{\omega (P):P~{\text{un}}~n{\text{-camino desde}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{hasta}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{un retorcido}}~n{\text{-camino desde}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{hasta}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{un no intersecante retorcido}}~n{\text{-camino desde}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{hasta}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&&+\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{un retorcido enredado}}~n{\text{-camino desde}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{hasta}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\omega (P)\\&&+\underbrace {\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{un retorcido enredado}}~n{\text{-camino desde}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{hasta}}~\left(b_{1},b_{2},...,b_{n}\right)\}} _{=0?}\\\end{array}}}$

Queda por demostrar que la suma de ${\displaystyle \mathrm {sign} (\sigma (P))\omega (P)}$ para todos los n-caminos retorcidos entrelazados se anula. Sea ${\displaystyle {\mathcal {E}}}$ el conjunto de n-caminos retorcidos entrelazados. Para establecer esto, se construye una involución ${\displaystyle f:{\mathcal {E}}\longrightarrow {\mathcal {E}}}$ con las propiedades ${\displaystyle \omega (f(P))=\omega (P)}$ y ${\displaystyle \mathrm {sign} (\sigma (f(P)))=-\mathrm {sign} (\sigma (P))}$ para todo ${\displaystyle P\in {\mathcal {E}}}$. Dada dicha involución, el resto

${\displaystyle \sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-camino desde}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{hasta}}~\left(b_{1},b_{2},...,b_{n}\right)\}=\sum _{P\in {\mathcal {E}}}\mathrm {sign} (\sigma (P))\omega (P)}$

en la suma anterior se reduce a 0, ya que sus sumandos se cancelan mutuamente (es decir, el sumando correspondiente a cada ${\displaystyle P\in {\mathcal {E}}}$ cancela al sumando correspondiente a ${\displaystyle f(P)}$).

Construcción de la involución: la idea tras la definición de la involución ${\displaystyle f}$ es elegir dos caminos que se intersecan dentro de un camino entrelazado e intercambiar sus colas después de su punto de intersección. En general, existen varios pares de caminos que se intersecan, que también pueden intersecarse varias veces. Por lo tanto, es necesario realizar una elección cuidadosa. Sea ${\displaystyle P=\left(P_{1},P_{2},...,P_{n}\right)}$ cualquier camino entrelazado trenzado de n. Entonces, ${\displaystyle f(P)}$ se define de la siguiente manera. Se denomina a un vértice lleno si pertenece a al menos dos de los caminos ${\displaystyle P_{1},P_{2},...,P_{n}}$. El hecho de que el grafo sea acíclico implica que esto equivale a aparecer al menos dos veces en todos los caminos.^[2]​ Dado que P está entrelazado, hay al menos un vértice lleno. Se selecciona el ${\displaystyle i\in \{1,2,\ldots ,n\}}$ más pequeño tal que ${\displaystyle P_{i}}$ contenga un vértice congestionado. Luego, se selecciona el primer vértice congestionado v en ${\displaystyle P_{i}}$ (primero en el sentido de encontrado primero al viajar por ${\displaystyle P_{i}}$), y se selecciona el j más grande tal que v pertenezca a ${\displaystyle P_{j}}$. La congestión de v implica que j > i. Denotando los dos caminos ${\displaystyle P_{i}}$ y ${\displaystyle P_{j}}$ como

${\displaystyle {\begin{array}{rcl}P_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {\mathbf {u} _{\alpha }\to u_{\alpha +1}\ldots \to u_{r}=b_{\sigma (i)}} ^{\mathrm {tail} ~i}\\P_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {\mathbf {v} _{\beta }\to v_{\beta +1}\ldots \to v_{s}=b_{\sigma (j)}} _{\mathrm {tail} ~j}\\\end{array}}}$

donde ${\displaystyle \sigma =\sigma (P)}$, y donde ${\displaystyle \alpha }$ y ${\displaystyle \beta }$ se eligen de modo que v sea el vértice ${\displaystyle \alpha }$-ésimo en ${\displaystyle P_{i}}$ y el vértice ${\displaystyle \beta }$-ésimo en ${\displaystyle P_{j}}$ (es decir, ${\displaystyle v=u_{\alpha }=v_{\beta }}$). Se establecen ${\displaystyle \alpha _{P}=\alpha }$ y ${\displaystyle \beta _{P}=\beta }$ y ${\displaystyle i_{P}=i}$ y ${\displaystyle j_{P}=j}$. Ahora se define el camino n retorcido ${\displaystyle f(P)}$ para que coincida con ${\displaystyle P}$, excepto por los componentes ${\displaystyle i}$ y ${\displaystyle j}$, que se reemplazan por

${\displaystyle {\begin{array}{rcl}P'_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {v_{\beta _{P}}\to v_{\beta _{P}+1}\ldots \to v_{s}=b_{\sigma (j)}} ^{\mathrm {tail} ~j}\\P'_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {u_{\alpha _{P}}\to u_{\alpha _{P}+1}\ldots \to u_{r}=b_{\sigma (i)}} _{\mathrm {tail} ~i}\\\end{array}}}$

Es evidente que ${\displaystyle f(P)}$ es un camino n torcido entrelazado. Siguiendo los pasos de la construcción, es fácil ver que ${\displaystyle i_{f(P)}=i_{P}}$, ${\displaystyle j_{f(P)}=j_{P}}$ y, además, que ${\displaystyle \alpha _{f(P)}=\alpha _{P}}$ y ${\displaystyle \beta _{f(P)}=\beta _{P}}$, de modo que aplicar ${\displaystyle f}$ de nuevo a ${\displaystyle f(P)}$ implica intercambiar las colas de ${\displaystyle f(P)_{i},f(P)_{j}}$ y dejar las demás componentes intactas. Por lo tanto, ${\displaystyle f(f(P))=P}$, y en consecuencia, ${\displaystyle f}$ es una involución. Queda por demostrar las propiedades de antisimetría deseadas:

De la construcción se desprende que ${\displaystyle \sigma (f(P))}$ coincide con ${\displaystyle \sigma =\sigma (P)}$, excepto que intercambia ${\displaystyle \sigma (i)}$ y ${\displaystyle \sigma (j)}$, obteniendo así ${\displaystyle \mathrm {sign} (\sigma (f(P)))=-\mathrm {sign} (\sigma (P))}$. Para demostrar que ${\displaystyle \omega (f(P))=\omega (P)}$, primero se calcula, recurriendo al intercambio de colas:

${\displaystyle {\begin{array}{rcl}\omega (P'_{i})\omega (P'_{j})&=&\left(\prod _{t=0}^{\alpha -1}\omega (u_{t},u_{t+1})\cdot \prod _{t=\beta }^{s-1}\omega (v_{t},v_{t+1})\right)\cdot \left(\prod _{t=0}^{\beta -1}\omega (v_{t},v_{t+1})\cdot \prod _{t=\alpha }^{r-1}\omega (u_{t},u_{t+1})\right)\\&=&\prod _{t=0}^{r-1}\omega (u_{t},u_{t+1})\cdot \prod _{t=0}^{s-1}\omega (v_{t},v_{t+1})\\&=&\omega (P_{i})\omega (P_{j}).\\\end{array}}}$

Por lo tanto, ${\displaystyle \omega (f(P))=\prod _{k=1}^{n}\omega (f(P)_{k})=\prod _{k=1,~k\neq i,j}^{n}\omega (P_{k})\cdot \omega (P'_{i})\omega (P'_{j})=\prod _{k=1,~k\neq i,j}^{n}\omega (P_{k})\cdot \omega (P_{i})\omega (P_{j})=\prod _{k=1}^{n}\omega (P_{k})=\omega (P)}$.

Así pues, se ha encontrado una involución con las propiedades deseadas y se ha completado la demostración del lema de Lindström-Gessel-Viennot.

Observación: argumentos similares al anterior aparecen en varias fuentes, con variaciones en cuanto a la elección de las colas a intercambiar. Una versión con el valor de j como el más pequeño (distinto de i) en lugar del más grande aparece en la referencia de Gessel-Viennot de 1989 (demostración del Teorema 1).

El lema de Lindström-Gessel-Viennot permite demostrar la equivalencia de las dos siguientes definiciones del polinomio de Schur. Dada una partición ${\displaystyle \lambda =\lambda _{1}+\cdots +\lambda _{r}}$ de n, el polinomio de Schur ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})}$ se define como:

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\sum _{T}w(T),}$

donde la suma es sobre todas las tablas de Young semiestándar T de forma λ, y el peso de una tabla T se define como el monomio obtenido al tomar el producto de la x_i indexada por las entradas i de T. Por ejemplo, el peso de la tabla

es ${\displaystyle x_{1}x_{3}x_{4}^{3}x_{5}x_{6}x_{7}}$.

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\det \left((h_{\lambda _{i}+j-i})_{i,j}^{r\times r}\right),}$

donde h_i son el polinomio simétrico homogéneo completo (donde h_i se entiende como 0 si i es negativo). Por ejemplo, para la partición (3,2,2,1), el determinante correspondiente es: ${\displaystyle s_{(3,2,2,1)}={\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}}.}$

Para demostrar la equivalencia, dada cualquier partición λ como la anterior, se consideran los r puntos iniciales ${\displaystyle a_{i}=(r+1-i,1)}$ y los r puntos finales ${\displaystyle b_{i}=(\lambda _{i}+r+1-i,n)}$ como puntos en la red ${\displaystyle \mathbb {Z} ^{2}}$, que adquiere la estructura de un grafo dirigido al afirmar que las únicas direcciones permitidas son ir uno a la derecha o uno hacia arriba; el peso asociado a cualquier arista horizontal con la altura i es x_i, y el peso asociado a una arista vertical es 1. Con esta definición, las r-tuplas de caminos de A a B son exactamente tablas de Young semiestándar de forma λ, y el peso de dicha r-tupla es el sumando correspondiente en la primera definición de los polinomios de Schur. Por ejemplo, con la tabla

,

se obtiene la correspondiente 4-tupla

Por otro lado, la matriz M es exactamente la matriz escrita anteriormente para D. Esto demuestra la equivalencia requerida (véase también el §4.5 del libro de Sagan, la Primera Demostración del Teorema 7.16.1 en el EC2 de Stanley, el §3.3 de la preimpresión de Fulmek en arXiv o el §9.13 de las notas de clase de Martin, para ligeras variaciones de este argumento).

También se puede utilizar el lema de Lindström-Gessel-Viennot para demostrar la fórmula de Cauchy–Binet y, en particular, la multiplicidad del determinante.

La aciclicidad de G es un supuesto esencial del lema de Lindström-Gessel-Viennot, que garantiza (en situaciones razonables) que las sumas ${\displaystyle e(a,b)}$ estén bien definidas y se incorpora por advección en la demostración (si G no es acíclica, entonces f podría transformar la autointersección de una trayectoria en la intersección de dos trayectorias distintas, lo que invalida el argumento de que f es una involución). Sin embargo, el artículo de Kelli Talaska de 2012 establece una fórmula que generaliza el lema a dígrafos arbitrarios. Las sumas ${\displaystyle e(a,b)}$ se sustituyen por series de potencias formales, y la suma sobre tuplas de trayectorias que no se intersecan se convierte ahora en una suma sobre conjuntos de trayectorias y ciclos que no se intersecan y que no se autointersecan, dividida por una suma sobre conjuntos de ciclos que no se intersecan. Se remite al lector al artículo de Talaska para más detalles.

• Teorema del árbol matricial

• Gessel, Ira M.; Viennot, Xavier G. (1989), Determinants, Paths and Plane Partitions, archivado desde el original el 17 de abril de 2017 .
• Lindström, Bernt (1973), On the vector representations of induced matroids, doi:10.1112/blms/5.1.85 .
• Sagan, Bruce E. (2001), The symmetric group, Springer .
• Stanley, Richard P. (1999), Enumerative Combinatorics, volume 2, CUP .
• Talaska, Kelli (2012), Determinants of weighted path matrices, arXiv:1202.3128v1 .
• Martin, Jeremy (2012), Lecture Notes on Algebraic Combinatorics .
• Fulmek, Markus (2010), Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively, arXiv:1010.3860v1 .