Teorema de Robertson-Seymour
En teoría de grafos , el teorema de Robertson-Seymour (también llamado teorema de grafo menor [1] ) establece que los grafos no dirigidos , parcialmente ordenados por la relación grafo menor , forman un cuasi ordenamiento bien . [2] De manera equivalente, cada familia de gráficos que se cierra bajo menores puede ser definida por un conjunto finito de menores prohibidos , de la misma manera que el teorema de Wagner caracteriza a los gráficos planares como aquellos que no tienen el gráfico completo K 5 o el gráfico bipartito completo K 3,3 como menores.
El teorema de Robertson-Seymour lleva el nombre de los matemáticos Neil Robertson y Paul D. Seymour , quienes lo probaron en una serie de veinte artículos que abarcan más de 500 páginas desde 1983 a 2004. [3] Antes de su demostración, el enunciado del teorema se conocía como La conjetura de Wagner después del matemático alemán Klaus Wagner , aunque Wagner dijo que nunca la conjeturó. [4]
Un resultado más débil para los árboles está implícito en el teorema del árbol de Kruskal , que fue conjeturado en 1937 por Andrew Vázsonyi y probado en 1960 de forma independiente por Joseph Kruskal y S. Tarkowski. [5]
A menor de un grafo no dirigido G es cualquier gráfico que se puede obtener de G por una secuencia de cero o más contracciones de bordes de G y deleciones de bordes y vértices de G . La relación menor forma un orden parcial en el conjunto de todas las gráficas finitas no dirigidas distintas, ya que obedece a los tres axiomas de órdenes parciales: es reflexiva (cada gráfica es una menor de sí misma), transitiva (una menor de una menor de G es en sí mismo un menor de G ), y antisimétrico (si dos gráficos G y Hson menores entre sí, entonces deben ser isomorfos ). Sin embargo, si los gráficos que son isomórficos pueden, no obstante, considerarse como objetos distintos, entonces el orden menor en los gráficos forma un preorden , una relación que es reflexiva y transitiva pero no necesariamente antisimétrica. [6]
Se dice que un preorden forma un cuasi-ordenamiento bien si no contiene ni una cadena descendente infinita ni un antichain infinito . [7] Por ejemplo, el orden habitual en los enteros no negativos es un buen cuasi-ordenamiento, pero el mismo orden en el conjunto de todos los enteros no lo es, porque contiene la cadena descendente infinita 0, -1, -2 , −3 ...
El teorema de Robertson-Seymour establece que las gráficas finitas no dirigidas y las gráficas menores forman un cuasi ordenamiento bien. La relación menor del gráfico no contiene ninguna cadena descendente infinita, porque cada contracción o eliminación reduce el número de aristas y vértices del gráfico (un número entero no negativo). [8] La parte no trivial del teorema es que no hay infinitos antichains, infinitos conjuntos de gráficos que no están relacionados entre sí por el orden menor. Si S es un conjunto de gráficos, y M es un subconjunto de S que contiene un gráfico representativo para cada clase de equivalencia de elementos mínimos (gráficos que pertenecen a S pero para los cuales ningún menor propio pertenece a S), entonces M forma un antichain; por lo tanto, una forma equivalente de enunciar el teorema es que, en cualquier conjunto infinito S de gráficos, debe haber solo un número finito de elementos mínimos no isomórficos.
