Los métodos sencillos del álgebra lineal son una herramienta sorprendentemente poderosa para demostrar resultados combinatorios. Algunos ejemplos de teoremas combinatorios con pruebas de álgebra lineal son el (débil) teorema del gráfico perfecto El Teorema de Frankl-Wilson y La desigualdad de Fisher .
¿Hay otros buenos ejemplos?
Otros ejemplos son la conjetura de Erdos-Moser (véase R. Proctor, Solution of two difficult problems with linear algebra, Amer. Math. Monthly 89 (1992), 721-734), algunos resultados en http://math.mit.edu/~rstan/312/linalg.pdf y el famoso resultado de Lovasz sobre la capacidad de Shannon de un ciclo de 5 y otros gráficos ( IEEE Trans. Inform. Theory 25 (1979), 1-7). Para un manuscrito preliminar de Babai y Frankl sobre este tema, véase http://www.cs.uchicago.edu/research/publications/combinatorics .
La AMS ha publicado un nuevo libro, Jiri Matousek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra. Información en http://www.ams.org/bookstore-getitem/item=STML-53
"Este volumen contiene una colección de ingeniosas aplicaciones matemáticas del álgebra lineal, principalmente en combinatoria, geometría y algoritmos".
Aquí hay un enlace a un artículo de Tricki que tiene algunos ejemplos más.
http://www.tricki.org/article/Dimension_arguments_in_combinatorics
El Lemma de Lindstrom-Gessel-Viennot utiliza el principio de reflexión en $S_n$ para decir que el número de familias de trayectorias de celosía que no se intersectan en el plano es igual al determinante de una matriz, de modo que el $i,j$ -es el número de caminos desde el $i$ a la fuente de $j$ El fregadero.
Esto no era una prueba de álgebra lineal. Sin embargo, este determinante se puede utilizar para enumerar las particiones del plano dentro de un $a\times b \times c~$ caja, a $q$ -enumerar particiones planas por peso, y contar los tilings de dominó de un diamante azteca. Los determinantes resultantes pueden manipularse y evaluarse de formas que son naturales en el álgebra lineal, pero no tan claras en los objetos, como la factorización de las matrices. Estas enumeraciones pueden verse como aplicaciones de resultados sencillos del álgebra lineal.
Notas:
Se definen los caminos de la red y se restringen las fuentes y los sumideros de manera que cualquier familia que no se intersecte debe ser una permutación par de los índices de la fuente a los índices del sumidero, normalmente la identidad.
Otros descubrieron independientemente este resultado, por ejemplo, Karlin y McGregor.
La misma idea se aplica al movimiento browniano.
Hoffman y Singleton demostraron que un grafo regular con circunferencia 5 y diámetro 2 tiene que tener grado 2, 3, 7 o 57. Si no recuerdo mal, la prueba utilizó propiedades espectrales de la matriz de adyacencia para producir alguna ecuación no polinómica para la que estas eran las soluciones enteras.
Hay ejemplos únicos de los tres primeros casos: el grado 2 es un pentágono, el grado 3 es el gráfico de Petersen y el grado 7 es el Gráfico Hoffman-Singleton . La existencia del gráfico de grado 57 sigue abierta (hasta donde yo sé).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
