La Matriz de Árbol sin el Teorema de la matriz

Question

Yo estoy enseñando una clase de introducción a la teoría de grafos curso en el Otoño, por lo que estoy emocionado porque me da la oportunidad de mejorar mi comprensión de gráficos (mi trabajo es en la topología). Lo más destacado para mí será para enseñar a la Matriz de Árbol Teorema, que creo que es el único lugar en el que el álgebra lineal es usado en el curso.

Vamos a κ(G) denota el número de árboles de expansión de G (la complejidad de G), y dejar que L(G) denota el Laplaciano de la matriz de G. por último, para un vértice v de G, sea L(v|v) indicar el Laplaciano de la matriz con la fila y la columna correspondiente a la v eliminados.

Matriz de Árbol Teorema: κ(G)= det L(v|v).

Parece una vergüenza para Álgebra Lineal para ser un prerrequisito para mi curso. De todos modos, no espero que la mayoría de mis estudiantes a ser gran Álgebra Lineal expertos. Porque mis alumnos no podría recordar cosas como Cauchy-Binet, pero sobre todo para que yo me siento que puedo entender realmente lo que te estoy enseñando, me pregunto cómo la Matriz de Árbol Teorema podría ser probado, sin mencionar jamás matrices. En un planeta con una fuerte combinatoria y donde álgebra lineal no había sido descubierto, ¿cómo podrían demostrar que la Matriz de Árbol Teorema?

El lado derecho de la Matriz de Árbol Teorema tiene sentido, sin mencionar jamás matrices, a través de la Lindström-Gessel-Viennot(-Karlin-MacGregor) Lema. Construir una gráfica de H, con una fuente y un sumidero correspondiente a cada vértice de G, por lo que la firma suma de borde pesos da las entradas de la Lagrangiana de la matriz de G (seguramente hay una inteligente manera estándar de hacer esto!) y definir el determinante de la H a la firma suma de todas las n-tuplas de la no-caminos se cruzan a partir de las fuentes de los sumideros. Esta interpretación de la determinante parece un buen tema para enseñar. Tal vez incluso hay una manera más fácil.

Cauchy-Binet se convierte en una primaria de la propiedad de los conjuntos de la no-caminos se cruzan en H, pero no puedo ver cómo liberar el resto de la prueba de la Matriz de Árbol Teorema de álgebra lineal.

Pregunta: ¿hay una prueba de la Matriz de Árbol Teorema de la que no hace mención de las matrices? Es lo suficientemente simple como que uno se pueda enseñar en una clase de introducción a la teoría de grafos curso?

Nota 1: Si el propósito de la Matriz de Árbol es el Teorema para calcular eficientemente la complejidad de un gráfico, a continuación, esquivando álgebra lineal es sin duda contraproducente, debido a que un factor determinante de manera eficiente puede ser calculado en tiempo polinomio. Pero, muy al lado de mi interés en "bien equipados" pruebas y mis objetivos docentes, tengo vagos sueños que son casi ciertamente tonterías acerca de una mejor comprensión de la Alexander polinomio como un quantum invariante a lo largo de las líneas de esta pregunta que podría factor a través de la Matriz de Árbol Teorema (o, más bien, una versión de Kirchhoff de la fórmula), y creo que claramente quiere quedarse en el diagrama mundo.

Nota 2: Este excelente post por Qiaochu Yuan sugiere que la respuesta a mi pregunta es en Aigner. Estoy de viaje ahora mismo, y la sección pertinente no está en la búsqueda de Libros de Google, así que no tengo acceso a Aigner para las próximas semanas. Si la memoria sirve, Aigner, todavía se utiliza álgebra lineal, pero tal vez me equivoque... de todos modos, si la respuesta resulta ser "buscar en Aigner", por favor downvote esta pregunta, o si podría resumir cómo se hace, yo sería más feliz. La respuesta seguramente va a llegar a ser "buscar en [algún lugar]" de todos modos, porque sin duda esto es fácil y bien conocidos (sólo que no lo saben)...

Answer 1

Una combinatoria prueba de la matriz de árbol teorema puede encontrarse en el artículo de D. Zeilberger Un enfoque combinatorio de álgebra matricial, La Matemática Discreta. 56 (1985), 61-72. La prueba utiliza sólo la interpretación de la determinante como un alternando suma más de permutaciones. Cada término corresponde a un dígrafo, y la de los bigramas que no corresponden a árboles de cancelar.

Answer 2

Se puede hacer sin Cauchy-Binet.

Si $e \in E(G)$, vamos a $G/e$ denotar el gráfico que se obtiene mediante la contratación de $e$ a un vértice. Deje $t(G)$ denotar el número de árboles de expansión en $G$. Entonces $$ t(G) = t(G\setminus e) + t(G/e). $$ Si $Q$ denota el Laplaciano de $G$ e $M[u]$ la matriz que obtenemos de la Laplaciano mediante la eliminación de la fila y la columna con índice de $u$ de $M$, es sencillo (utilizando el estándar determinental operaciones) para mostrar que $$ \det(Q, G)[u] = \det(Q, G\setminus e)[u] +\det P(G/e)[u] $$ Así, el resultado de la siguiente manera por inducción.

Esta prueba se presenta en la Sección 13.2 de uno de mis libros favoritos sobre algebraicas teoría de grafos :-) estoy segura de que muchas otras personas han llegado con él. Proporciona una excusa para hablar acerca de algunos de los interesantes gráfico de los parámetros de thatn puede ser calculada por la eliminación de la contracción (o es la eliminación de la contracción?)

Answer 3

Interesante pregunta! Hay un modo elemental para demostrar que la matriz de árbol teorema usando sólo el razonamiento combinatorio y bijections. El resultado que me estoy refiriendo es: el número de árboles de expansión en un gráfico de $G$ es el mismo que el número de $G$-aparcamiento funciones. Hay un bijective prueba de este hecho en "Una familia de bijections entre G-aparcamiento funciones y árboles de expansión" por D. Chebikin y P. Pylyavskyy. Ahora, ¿qué hacen estas $G$-aparcamiento funciones tienen que ver con el determinante de la laplaciano $L(G)$?

Resulta que $G$-aparcamiento funciones son representantes de los elementos en la cokernel del mapa $\mathbb Z^{n}\to \mathbb Z^n$ dado por la multiplicación por $L(G)$ donde $n$ es el número de vértices en $G$. Este cokernel aparece en un montón de lugares y se le suele llamar el grupo Crítico de $G$ o de la pila de arena grupo de $G$ (o, según algunos autores, el Jacobiano de grupo o grupo de Picard) y es bien conocido por tener la misma cardinalidad como el número de árboles de expansión de $G$. Cualquier bijection entre estos no se canónica, porque no hay elección canónica de árbol de expansión en $G$, por lo que todos bijections, deben tomar decisiones en algún momento.

Tan lejos como bijections con otros cokernels, como el linfogranuloma venéreo o Kasteleyn-Percu, no sé si se puede hacer perfectamente en la gran generalidad. Sé que contar árboles de expansión puede ser traducido a contar perfecto elecciones para grafos planares, por ejemplo. Tal vez se extiende a otras clases de niza.

Que dijo, aunque este enfoque evita mencionar las matrices de Cauchy-Binet y todo eso, sería terrible para una primera prueba de la matriz de árbol teorema. Creo que esto es similar a tratar de enseñar en la escuela elemental de la prueba del teorema de los números primos en un primer curso de teoría analítica de números. Con menos herramientas no necesariamente conducen a más iluminación. :)

Answer 4

Le pregunté a Daniel Spielman una pregunta relacionada, que era lo que el más conceptual de la prueba de la matriz de árbol teorema es, sin recurrir a los números reales. Él sugirió que estas notas por Nikhil Srivastava.

Las Matrices se utilizan, pero en realidad el álgebra lineal a mí me parece que se puede convertir en la combinatoria de los gráficos de una manera sencilla, de modo que su respuesta constituye una buena respuesta a esta pregunta así. En cualquier caso, es un buen corto conceptual de la prueba de la matriz de árbol teorema que yo no había conocido.