Lema de Lindström-Gessel-Viennot

Cuenta el número de tuplas de caminos reticulares que no se intersecan

En matemáticas, el lema de Lindström-Gessel-Viennot proporciona una forma de contar la cantidad de tuplas de caminos reticulares que no se intersecan o, de manera más general, caminos en un grafo dirigido. Fue demostrado por Gessel-Viennot en 1985, basándose en un trabajo previo de Lindström publicado en 1973.

Declaración

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. Considere los vértices base y los vértices de destino , y asigne también un peso 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 el producto de los pesos de las aristas del camino. Para dos vértices cualesquiera a y b , escriba e ( a , b ) para la suma de todos los caminos de a a b . Esto está bien definido si entre dos puntos cualesquiera hay solo un número finito de caminos; pero incluso en el caso general, esto puede estar bien definido bajo algunas circunstancias (como que todos los pesos de arista sean indeterminados formales distintos por pares y se consideren como una serie de potencias formales ). Si uno asigna el peso 1 a cada arista, entonces e ( a , b ) cuenta el número de caminos de a a b . ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$ ${\displaystyle \omega _{e}}$ ${\displaystyle \omega (P)}$ ${\displaystyle e(a,b)=\sum _{P:a\to b}\omega (P)}$ ${\displaystyle e(a,b)}$

Con esta configuración, escribe

${\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 que no se intersecan de A a B significa una n -tupla ( P ₁ , ..., P _n ) de caminos en G con las siguientes propiedades:

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

Dada tal n- tupla ( P ₁ , ..., P _n ), denotamos por la permutación de de la primera condición. ${\displaystyle \sigma (P)}$ ${\displaystyle \sigma }$

El lema de Lindström–Gessel–Viennot establece entonces 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 comienzan en A y terminan en B , cada uno afectado con el signo de la permutación correspondiente de , dada al tomar como . ${\displaystyle (1,2,\ldots ,n)}$ ${\displaystyle P_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{\sigma (i)}}$

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

Prueba

Para demostrar el lema de Lindström–Gessel–Viennot, primero introducimos algo de notación.

Un n -camino desde una n -tupla de vértices de G a una n -tupla de vértices de G significará una n -tupla de caminos en G , y cada uno de ellos conduce desde a . Este n -camino se llamará no intersecante solo en caso de que los caminos P _i y P _j no tengan dos vértices en común (incluidos los puntos finales) siempre que . De lo contrario, se llamará entrelazado . ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ ${\displaystyle P_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle i\neq j}$

Dada una ruta n , el peso de esta ruta n se define como el producto . ${\displaystyle P=(P_{1},P_{2},\ldots ,P_{n})}$ ${\displaystyle \omega (P)}$ ${\displaystyle \omega (P_{1})\omega (P_{2})\cdots \omega (P_{n})}$

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

Recordando la definición de M , podemos expandir det M como una suma con signo de permutaciones; así obtenemos

${\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{an}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{a twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{a non-intersecting twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&&+\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\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{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}} _{=0?}\\\end{array}}}$

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

${\displaystyle \sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\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 entre sí (es decir, el sumando correspondiente a cada uno cancela el sumando correspondiente a ). ${\displaystyle P\in {\mathcal {E}}}$ ${\displaystyle f(P)}$

Construcción de la involución: La idea detrás de la definición de la involución es elegir dos caminos que se intersectan dentro de un camino entrelazado, e intercambiar sus colas después de su punto de intersección. En general, hay varios pares de caminos que se intersectan, que también pueden intersecarse varias veces; por lo tanto, se debe hacer una elección cuidadosa. Sea cualquier camino entrelazado torcido n . Entonces se define de la siguiente manera. Llamamos a un vértice abarrotado si pertenece al menos a dos de los caminos . El hecho de que el grafo sea acíclico implica que esto es equivalente a "aparecer al menos dos veces en todos los caminos". ^[1] Como P está entrelazado, hay al menos un vértice abarrotado. Escogemos el más pequeño tal que contiene un vértice abarrotado. Luego, escogemos el primer vértice abarrotado v en ("primero" en el sentido de "encontrado primero al viajar a lo largo de "), y escogemos el j más grande tal que v pertenece a . El abarrotamiento de v implica j > i . Escribimos los dos caminos y como ${\displaystyle f}$ ${\displaystyle P=\left(P_{1},P_{2},...,P_{n}\right)}$ ${\displaystyle f(P)}$ ${\displaystyle P_{1},P_{2},...,P_{n}}$ ${\displaystyle i\in \{1,2,\ldots ,n\}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$

${\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 , y donde y se eligen de manera que v sea el -ésimo vértice a lo largo de y el -ésimo vértice a lo largo de (es decir, ). Establecemos y y y . Ahora definamos la ruta n torcida para que coincida con excepto para los componentes y , que se reemplazan por ${\displaystyle \sigma =\sigma (P)}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle P_{i}}$ ${\displaystyle \beta }$ ${\displaystyle P_{j}}$ ${\displaystyle v=u_{\alpha }=v_{\beta }}$ ${\displaystyle \alpha _{P}=\alpha }$ ${\displaystyle \beta _{P}=\beta }$ ${\displaystyle i_{P}=i}$ ${\displaystyle j_{P}=j}$ ${\displaystyle f(P)}$ ${\displaystyle P}$ ${\displaystyle i}$ ${\displaystyle j}$

${\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 de inmediato que es un camino n entrelazado y retorcido . Al seguir los pasos de la construcción, es fácil ver que , y además que y , de modo que aplicar de nuevo a implica intercambiar las colas de y dejar los otros componentes intactos. Por lo tanto . Por lo tanto, es una involución. Queda por demostrar las propiedades de antisimetría deseadas: ${\displaystyle f(P)}$ ${\displaystyle i_{f(P)}=i_{P}}$ ${\displaystyle j_{f(P)}=j_{P}}$ ${\displaystyle \alpha _{f(P)}=\alpha _{P}}$ ${\displaystyle \beta _{f(P)}=\beta _{P}}$ ${\displaystyle f}$ ${\displaystyle f(P)}$ ${\displaystyle f(P)_{i},f(P)_{j}}$ ${\displaystyle f(f(P))=P}$ ${\displaystyle f}$

De la construcción se puede ver que coincide con excepto que intercambia y , por lo que da como resultado . Para demostrar que primero calculamos, apelando al intercambio de cola ${\displaystyle \sigma (f(P))}$ ${\displaystyle \sigma =\sigma (P)}$ ${\displaystyle \sigma (i)}$ ${\displaystyle \sigma (j)}$ ${\displaystyle \mathrm {sign} (\sigma (f(P)))=-\mathrm {sign} (\sigma (P))}$ ${\displaystyle \omega (f(P))=\omega (P)}$

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

De esta forma hemos encontrado una involución con las propiedades deseadas y hemos completado la prueba 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 qué colas cambiar. Una versión con j más pequeño (desigual a i ) en lugar de más grande aparece en la referencia de Gessel-Viennot 1989 (prueba del Teorema 1).

Aplicaciones

Polinomios de Schur

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

• ${\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 las x _i indexadas por las entradas i de T . Por ejemplo, el peso de la tablaes . ${\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 los polinomios simétricos homogéneos completos ( entendiéndose h _i 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 probar la equivalencia, dada cualquier partición λ como la anterior, se consideran los r puntos iniciales y los r puntos finales como puntos en la red , 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 borde horizontal a la altura i es x _i , y el peso asociado a un borde 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 ${\displaystyle a_{i}=(r+1-i,1)}$ ${\displaystyle b_{i}=(\lambda _{i}+r+1-i,n)}$ ${\displaystyle \mathbb {Z} ^{2}}$, se obtiene la 4 -tupla correspondiente

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

La fórmula de Cauchy-Binet

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.

Generalizaciones

La fórmula de Talaska

La aciclicidad de G es un supuesto esencial del lema de Lindström–Gessel–Viennot; garantiza (en situaciones razonables) que las sumas estén bien definidas y se incorpora a la prueba (si G no es acíclica, entonces f podría transformar una autointersección de un camino en una intersección de dos caminos distintos, lo que rompe 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 se reemplazan por series de potencias formales y la suma sobre tuplas de caminos que no se intersecan ahora se convierte en una suma sobre colecciones de caminos y ciclos que no se intersecan y que no se autointersecan, dividida por una suma sobre colecciones de ciclos que no se intersecan. Se remite al lector al artículo de Talaska para obtener más detalles. ${\displaystyle e(a,b)}$ ${\displaystyle e(a,b)}$

Véase también

• Teorema del árbol matricial

Referencias

1. Si el gráfico no fuera acíclico, el "hacinamiento" podría cambiar después de aplicar  ; esta prueba no funcionaría y el lema en realidad se volvería totalmente falso. ${\displaystyle f}$

• Gessel, Ira M. ; Viennot, Xavier G. (1989), Determinantes, caminos y particiones de planos (PDF) , archivado desde el original (PDF) el 17 de abril de 2017
• Lindström, Bernt (1973), Sobre las representaciones vectoriales de matroides inducidos , doi :10.1112/blms/5.1.8 (inactivo 2024-10-17){{citation}}: CS1 maint: DOI inactive as of October 2024 (link)
• Sagan, Bruce E. (2001), El grupo simétrico , Springer
• Stanley, Richard P. (1999), Combinatoria enumerativa, volumen 2 , CUP
• Talaska, Kelli (2012), Determinantes de matrices de rutas ponderadas , arXiv : 1202.3128v1
• Martin, Jeremy (2012), Apuntes de clase sobre combinatoria algebraica (PDF)
• Fulmek, Markus (2010), Ver los determinantes como caminos reticulares que no se intersecan produce identidades determinantes clásicas de manera biyectiva , arXiv : 1010.3860v1