¿Cuáles son los triunfos externos de la teoría de los matroides?

Question

Como abstracción relativamente nueva, los matroides gozan claramente de una rica teoría en sí mismos y también ofrecen un punto de vista que sugiere interesantes analogías y aclara aspectos de los fundamentos de temas venerables.

Dicho esto, una métrica muy dura para juzgar tal abstracción podría preguntar qué resultados importantes en otras áreas parecen depender razonablemente de los conocimientos obtenidos primero en la búsqueda de la teoría pura. Así que me gustaría saber, por favor, qué resultados específicos citaría un partidario de la teoría de los matrices como las mejores demostraciones del poder de la teoría de los matrices en el ámbito más amplio de las matemáticas.

(Me doy cuenta de que los matemáticos de un campo a veces absorben ideas de otro campo, y luego las traducen a su idioma preferido, lo que puede oscurecer la deuda. Así que los artículos importantes que de alguna manera no podrían existir sin la teoría de los matroides deberían contar aquí aunque nunca mencionen explícitamente los matroides).

Answer 1

He aquí dos de esos triunfos. Hay muchos otros.

(1) Los matroides orientados fueron utilizados por Gelfand y MacPherson para dar una fórmula combinatoria para las clases de Pontrjagin, un problema abierto desde hace tiempo. Véase http://www.ams.org/journals/bull/1992-26-02/S0273-0979-1992-00282-3/home.html . Ha habido muchos más avances en este ámbito.

(2) Citando la primera frase de la Math Review 88f:14045, "en este trabajo los autores descubren una notable conexión entre la geometría de las celdas de Schubert en un colector grassmanniano, matroide y los poliedros convexos". Los autores son Gelfand, Goresky MacPherson y Serganova. Este trabajo inició (creo) el estudio de los de los politopos matroidales, que se ha convertido en una gran industria.

Answer 2

Hace muchos años, aprendí de Vladimir Arnold que los resultados más importantes de las matemáticas parecen después triviales porque se convierten en definiciones (puso como ejemplo el teorema de Pitágoras y el producto escalar). Has formulado tu pregunta con mucho cuidado, para evitar este escollo, pero ahí está la respuesta. No sólo la teoría de los matroides nació como una abstracción de los resultados básicos del álgebra lineal, sino que su contribución más importante es la cristalización de lo que es importante y lo que es posible en los campos vecinos. He aquí mi ejemplo favorito.

Teorema de universalidad de Mnёv nació como un resultado fundamental sobre los espacios de realización (moduli) de los matroides. El propio Mnёv lo utilizó para demostrar un delicado teorema sobre realizaciones de poliedros combinatorios. Kapovich y Millson universalidad de los vínculos el teorema de Vakil Ley de Murphy y Belkale-Brosnan (fuerte) refutación de la conjetura de Kontsevich seguido. Aunque algunos de estos resultados no utilizan explícitamente el teorema de Mnёv, éste sirvió de importante motivación.

Answer 3

He aquí un ejemplo de la teoría poliédrica. Una matriz $A \in \mathbb{R}^{n \times m}$ es totalmente unimodular si cada submatriz cuadrada de $A$ tiene un determinante $1, -1,$ o $0$ . Las matrices totalmente unimodulares son objetos importantes en la teoría de la optimización ya que entero pueden resolverse de forma eficiente cuando la matriz de restricciones es totalmente unimodular. Es decir, si $A$ es una matriz totalmente unimodular, y $b$ es un vector entero, entonces el poliedro

$P:=\lbrace x : Ax \leq b \rbrace$ es integral (el casco convexo de los puntos integrales dentro de $P$ es $P$ mismo). Esto motiva la siguiente pregunta importante.

Pregunta: ¿Cómo se puede reconocer eficazmente cuándo una matriz es totalmente unimodular?

Aquí es donde entran los matroides. Un matroide es regular si se puede representar sobre cualquier campo. En 1980, Seymour demostró un teorema de descomposición para matroides regulares. Teorema de descomposición de Seymour afirma que todo matroide regular puede obtenerse a partir de matroides gráficos, matroides cográficos y un matroide específico $R_{10}$ utilizando sumas de 1, 2 y 3. Truemper demostró que el teorema de descomposición de Seymour conduce realmente a un algoritmo de tiempo polinómico para reconocer matrices totalmente unimodulares. Incluso ahora, creo que el único algoritmo de reconocimiento de este tipo utiliza el teorema de descomposición.

Answer 4

Un complejo celular $K$ es un $m$ -obstructor si el subcomplejo $K\circledast K$ de la unión $K*K$ consistente en las uniones de celdas disjuntas es PL homeomorfo a la $(m+1)$ -esfera. Flores (1933) demostró que toda $m$ -el constructor no se incrusta en $\Bbb R^m$ (esto es una consecuencia fácil del teorema de Borsuk-Ulam), y encontró algunas $n$ -dimensional $2n$ -obstructores: los $n$ -esqueleto $F_n$ de la $(2n+2)$ -simplex, y la unión $F_0*\dots*F_0$ de $n+1$ copias del conjunto de tres puntos. Argumentos similares demuestran que cada $n$ -de la forma $F_{i_1}*\dots*F_{i_k}$ es un $2n$ -obstructor (Gruenbaum, 1969).

Utilizando matroides , Sarkaria probado que estas uniones son las sólo $2n$ -obstructores entre todos $n$ -dimensional simplicial complejos. Me gustaría poder rehacer este resultado sin matroides, ¡pero desgraciadamente no puedo!

La atracción de $n$ -dimensional $2n$ -obstructores es que si bien no se incrustan en $\Bbb R^{2n}$ Todos sus derechos menores (en particular, los subcomplejos propios). Ahora se trata de extender los métodos de Sarkaria a los complejos no simplificados, ya que los obstructores no simplificados son mucho más interesantes que los simplificados.

Answer 5

Tal vez no sean los resultados más potentes, pero aquí hay algunas aplicaciones bastante pulcras y bastante recientes.

La desigualdad de Ingleton relaciona los rangos de ciertas combinaciones de subconjuntos del conjunto base. Es válida para cualquier matroide representable, pero no para todos los matroides no representables. Por ejemplo, puede utilizarse para demostrar que el matroide de Vámos no es representable.

La desigualdad de Ingleton ha encontrado su camino en la teoría de la información, en el contexto de la entropía de Shannon. He aquí un ejemplo: http://arxiv.org/abs/0905.1519

El matroide de Vámos proporciona un contraejemplo a una conjetura sobre conjuntos representables por desigualdades matriciales lineales: http://arxiv.org/abs/1004.1382

El otro día, un colega me mostró una prueba bastante bonita de un resultado de álgebra lineal. La prueba utilizaba la unión de matrices.