Sea G un grafo acíclico dirigido localmente finito . Esto significa que cada vértice tiene un grado finito y que G no contiene ciclos dirigidos. Considere los vértices base y vértices de destino , y también asignar un peso a cada borde dirigido e . Se supone que estos pesos de borde pertenecen a algún anillo conmutativo . Para cada camino dirigido P entre dos vértices, seaser el producto de los pesos de los bordes del camino. Para cualquier par de vértices de un y b , escritura e ( un , b ) para la sumaen todos los caminos de a a b . Esto está bien definido si entre dos puntos cualesquiera sólo hay un número finito de caminos; pero incluso en el caso general, esto puede estar bien definido en algunas circunstancias (como que todos los pesos de los bordes sean indeterminados formales distintos por pares, ysiendo considerado como una serie de poder formal). Si se asigna el peso 1 a cada borde, entonces e ( a , b ) cuenta el número de trayectorias desde a hasta b .
Con esta configuración, escriba
- .
Una n- tupla de caminos que no se cruzan de A a B significa un n -tuplo ( P 1 , ..., P n ) de caminos en G con las siguientes propiedades:
- Existe una permutación de de tal manera que, para cada i , el camino P i es un camino desde a .
- Cuando sea , los caminos P i y P j no tienen dos vértices en común (ni siquiera extremos).
Dada tal n- tupla ( P 1 , ..., P n ), denotamos por la permutación de desde 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 1 , ..., P n ) de las trayectorias que no se cruzan de A a B :
Es decir, el determinante de M cuenta los pesos de todas las n tuplas de caminos que no se cruzan comenzando en A y terminando en B , cada uno afectado con el signo de la permutación correspondiente de, dada por tomando a .
En particular, si la única permutación posible es la identidad (es decir, cada n tupla de trayectorias que no se cruzan desde A a B toma un i a Ib i para cada i ) y tomamos los pesos para ser 1, entonces det ( M ) es exactamente el número de no intersección n -tuplas de caminos a partir de a y terminando en B .
Para probar el lema de Lindström-Gessel-Viennot, primero introducimos alguna notación.
Una n- ruta de una n- tuplade vértices de G a una n- tuplade vértices de G significará una n- tuplade caminos en G , con cada va 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á enredado .
Dado un n- camino, el peso de esta n- ruta se define como el producto.
Un n- camino retorcido de una n- tuplade vértices de G a una n- tuplade vértices de G significará un n- camino desde a por alguna permutación en el grupo simétrico . Esta permutaciónserá llamado el giro de este n- camino retorcido , y denotado por(donde P es el n- camino). Esto, por supuesto, generaliza la notación introducido antes.
Recordando la definición de M , podemos expandir det M como una suma con signo de permutaciones; así obtenemos
Queda por mostrar que la suma desobre todos los n- senderos retorcidos enredados desaparece. Dejardenotar el conjunto de n- caminos entrelazados y retorcidos . Para establecer esto, construiremos una involución con las propiedades y para todos . Dada tal involución, el resto del término
en la suma anterior se reduce a 0, ya que sus sumandos se cancelan entre sí (es decir, el sumando correspondiente a cada cancela el sumando correspondiente a ).
Construcción de la involución: la idea detrás de la definición de la involución es elegir dos caminos que se cruzan dentro de un camino entrelazado y cambiar sus colas después de su punto de intersección. En general, hay varios pares de caminos que se cruzan, que también pueden cruzarse varias veces; por lo tanto, es necesario hacer una elección cuidadosa. Dejarser cualquier n- camino retorcido enredado. Luegose define de la siguiente manera. Llamamos a un vértice abarrotado si pertenece al menos a dos de los caminos. Dado que P está entrelazado, hay al menos un vértice abarrotado. Elegimos los más pequeños tal que contiene un vértice abarrotado. Luego, elegimos el primer vértice abarrotado v en ("primero" en el sentido de "encontrado primero al viajar por "), y seleccionamos el j más grande de modo que v pertenece a. El hacinamiento de v implica j > i . Escribe los dos caminos y como
dónde , y donde y se eligen de tal manera que v es el-th vértice a lo largo y el -th vértice a lo largo (es decir, ). Establecimos y y y . Ahora defina el n- camino retorcido para coincidir con excepto por componentes y , que son reemplazados por
Inmediatamente queda claro que es un n- camino entrelazado y retorcido . Pasando por los pasos de la construcción, es fácil ver que, y ademas que y , de modo que aplicando de nuevo a implica intercambiar las colas de y dejando los demás componentes intactos. Por eso. Por lo tantoes una involución. Queda por demostrar las propiedades antisimetría deseadas:
Desde la construcción se puede ver que coincide con excepto que cambia y , cediendo así . Para mostrar que primero calculamos, apelando al tail-swap
Por eso .
Así hemos encontrado una involución con las propiedades deseadas y hemos completado la demostración del lema de Lindström-Gessel-Viennot.
Observación. Argumentos similares al anterior aparecen en varias fuentes, con variaciones con respecto a la elección de qué colas cambiar. En la referencia de Gessel-Viennot 1989 aparece una versión con j más pequeña (desigual a i ) en lugar de la más grande (prueba del teorema 1).
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ónde n , el polinomio de Schur Puede ser definido como:
donde la suma es sobre todos semiestándar joven cuadros T de forma λ , y el peso de un cuadro T se define como el monomio obtenido tomando el producto de la x i indexada por las entradas i de T . Por ejemplo, el peso del cuadro es .
donde h i son los polinomios simétricos homogéneos completos (con h i entendido como 0 si i es negativo). Por ejemplo, para la partición (3,2,2,1), el determinante correspondiente es
Para probar la equivalencia, dada cualquier partición λ como arriba, se consideran los r puntos de partiday los puntos finales r, como puntos en la celosía , que adquiere la estructura de un grafo dirigido al afirmar que las únicas direcciones permitidas son ir hacia la derecha o 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, r -tuplas de caminos de A a B son exactamente cuadros de Young semiestándar de forma λ , y el peso de tal r -tupla es el sumando correspondiente en la primera definición de los polinomios de Schur. Por ejemplo, con el cuadro, se obtiene la tupla 4 correspondiente
Por otro lado, la matriz M es exactamente la matriz escrito anteriormente para D . Esto muestra la equivalencia requerida. (Véase también §4.5 en el libro de Sagan, o la Primera prueba del teorema 7.16.1 en EC2 de Stanley, o §3.3 en la preimpresión arXiv de Fulmek, o §9.13 en las notas de la conferencia 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 probar la fórmula de Cauchy-Binet y, en particular, la multiplicatividad del determinante.
Fórmula de Talaska
La aciclicidad de G es una suposición esencial en el lema de Lindström-Gessel-Viennot; garantiza (en situaciones razonables) que las sumasestán bien definidas y se advierte en la demostración (si G no es acíclico, entonces f podría transformar una auto-intersección de una ruta en una intersección de dos rutas distintas, 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 sumasse reemplazan por series de potencias formales, y la suma de las tuplas de trayectorias que no se intersectan ahora se convierte en una suma de las colecciones de trayectorias y ciclos que no se intersecan y que no se intersecan, dividida por una suma de las colecciones de ciclos que no se intersecan. Se remite al lector al artículo de Talaska para obtener más detalles.