Teorema de Robertson-Seymour

En teoría de grafos , el teorema de Robertson-Seymour (también llamado teorema de los menores de grafos ^{[ 1 ]} ) establece que los grafos no dirigidos , parcialmente ordenados por la relación de menores de grafos , forman un cuasiordenamiento bien definido . ^{[ 2 ]} De forma equivalente, toda familia de grafos que es cerrada bajo la toma de menores puede definirse mediante un conjunto finito de menores prohibidos , de la misma manera que el teorema de Wagner caracteriza a los grafos planares como aquellos que no tienen el grafo completo.${\displaystyle K_{5}}$o el grafo bipartito completo${\displaystyle K_{3,3}}$como menores de edad.

El teorema de Robertson-Seymour recibe su nombre de los matemáticos Neil Robertson y Paul D. Seymour , quienes lo demostraron en una serie de veinte artículos que abarcan más de 500 páginas, publicados entre 1983 y 2004. ^{[ 3 ]} Antes de su demostración, el enunciado del teorema se conocía como la conjetura de Wagner, en honor al matemático alemán Klaus Wagner , aunque Wagner afirmó no haberla conjeturado nunca. ^{[ 4 ]}

Un resultado más débil para árboles está implícito en el teorema del árbol de Kruskal , que fue conjeturado en 1937 por Andrew Vázsonyi y demostrado en 1960 independientemente por Joseph Kruskal y S. Tarkowski. ^{[ 5 ]}

Un menor de un grafo no dirigido${\displaystyle G}$es cualquier gráfico que se pueda obtener de${\displaystyle G}$mediante una secuencia de cero o más contracciones de aristas de${\displaystyle G}$y eliminaciones de aristas y vértices de${\displaystyle G}$La relación de menor forma un orden parcial en el conjunto de todos los grafos finitos no dirigidos distintos, ya que obedece los tres axiomas de los órdenes parciales: es reflexiva (todo grafo es un menor de sí mismo), transitiva (un menor de un menor de${\displaystyle G}$es en sí mismo un menor de${\displaystyle G}$), y antisimétrico (si dos gráficos${\displaystyle G}$y${\displaystyle G}$Si son menores entre sí, entonces deben ser isomorfos . Sin embargo, si los grafos que son isomorfos pueden considerarse como objetos distintos, entonces el orden de los menores en los grafos forma un preorden , una relación que es reflexiva y transitiva pero no necesariamente antisimétrica. ^{[ 6 ]}

Se dice que un preorden forma un buen cuasiordenamiento si no contiene ni una cadena descendente infinita ni una anticadena infinita . ^{[ 7 ]} Por ejemplo, el orden usual en los enteros no negativos es un buen cuasiordenamiento, pero el mismo orden en el conjunto de todos los enteros no lo es, porque contiene la cadena descendente infinita 0, − 1, − 2, − 3... Otro ejemplo es el conjunto de enteros positivos ordenado por divisibilidad , que no tiene cadenas descendentes infinitas, pero donde los números primos constituyen una anticadena infinita.   

El teorema de Robertson-Seymour establece que los grafos no dirigidos finitos y los menores de grafos forman un buen cuasiordenamiento. La relación de menores de grafos no contiene ninguna cadena descendente infinita, porque cada contracción o eliminación reduce el número de aristas y vértices del grafo (un entero no negativo). ^{[ 8 ]} La parte no trivial del teorema es que no existen anticadenas infinitas, conjuntos infinitos de grafos que no estén relacionados entre sí por el ordenamiento de menores. Si${\displaystyle {\mathcal {S}}}$es un conjunto de gráficos, y${\displaystyle {\mathcal {M}}}$es un subconjunto de${\displaystyle {\mathcal {S}}}$que contiene un gráfico representativo para cada clase de equivalencia de elementos mínimos (gráficos que pertenecen a${\displaystyle {\mathcal {S}}}$pero para lo cual no pertenece ningún menor propio${\displaystyle {\mathcal {S}}}$), entonces${\displaystyle {\mathcal {M}}}$forma una anticadena; por lo tanto, una forma equivalente de enunciar el teorema es que, en cualquier conjunto infinito${\displaystyle {\mathcal {S}}}$En los grafos, debe haber solo un número finito de elementos mínimos no isomorfos.

Otra forma equivalente del teorema es que, en cualquier conjunto infinito${\displaystyle {\mathcal {S}}}$de grafos, debe haber un par de grafos uno de los cuales es menor del otro. ^{[ 8 ]} La afirmación de que todo conjunto infinito tiene un número finito de elementos mínimos implica esta forma del teorema, pues si solo hay un número finito de elementos mínimos, entonces cada uno de los grafos restantes debe pertenecer a un par de este tipo con uno de los elementos mínimos. Y en la otra dirección, esta forma del teorema implica la afirmación de que no puede haber anticadenas infinitas, porque una anticadena infinita es un conjunto que no contiene ningún par relacionado por la relación de menor.

Una familia${\displaystyle {\mathcal {F}}}$Se dice que un conjunto de grafos es cerrado bajo la operación de tomar menores si cada menor de un grafo en${\displaystyle {\mathcal {F}}}$también pertenece a${\displaystyle {\mathcal {F}}}$. Si${\displaystyle {\mathcal {F}}}$es una familia cerrada menor, entonces deja${\displaystyle {\mathcal {S}}}$ser la clase de grafos que no están en${\displaystyle {\mathcal {F}}}$(el complemento de${\displaystyle {\mathcal {F}}}$). Según el teorema de Robertson-Seymour, existe un conjunto finito${\displaystyle {\mathcal {H}}}$de elementos mínimos en${\displaystyle {\mathcal {S}}}$Estos elementos mínimos forman una caracterización gráfica prohibida de${\displaystyle {\mathcal {F}}}$: los gráficos en${\displaystyle {\mathcal {F}}}$son exactamente los gráficos que no tienen ningún gráfico en${\displaystyle {\mathcal {H}}}$como menor. ^{[ 9 ]} Los miembros de${\displaystyle {\mathcal {H}}}$Se les llama menores excluidos (o menores prohibidos , o menores obstrucciones mínimas ) para la familia.${\displaystyle {\mathcal {F}}}$.

Por ejemplo, los grafos planares son cerrados bajo la operación de tomar menores: contraer una arista en un grafo planar, o eliminar aristas o vértices del grafo, no puede destruir su planaridad. Por lo tanto, los grafos planares tienen una caracterización de menores prohibida, que en este caso viene dada por el teorema de Wagner : el conjunto${\displaystyle {\mathcal {H}}}$de grafos no planares mínimos menores contiene exactamente dos grafos, el grafo completo${\displaystyle K_{5}}$y el grafo bipartito completo${\displaystyle K_{3,3}}$y los grafos planares son precisamente los grafos que no tienen un menor en el conjunto${\displaystyle {\mathcal {H}}=\{K_{5},K_{3,3}\}.}$

La existencia de caracterizaciones menores prohibidas para todas las familias de grafos cerradas en menores es una forma equivalente de enunciar el teorema de Robertson-Seymour. Porque, supongamos que cada familia cerrada en menores${\displaystyle {\mathcal {F}}}$tiene un conjunto finito${\displaystyle {\mathcal {H}}}$de menores prohibidos mínimos, y dejar${\displaystyle {\mathcal {S}}}$Sea cualquier conjunto infinito de grafos. Determinar${\displaystyle {\mathcal {F}}}$de${\displaystyle {\mathcal {S}}}$como la familia de grafos que no tienen un menor en${\displaystyle {\mathcal {S}}}$. Entonces${\displaystyle {\mathcal {F}}}$es cerrado bajo la regla de los menores y tiene un conjunto finito.${\displaystyle {\mathcal {H}}}$de menores prohibidos mínimos. Deje${\displaystyle {\mathcal {C}}}$ser el complemento de${\displaystyle {\mathcal {F}}}$.${\displaystyle {\mathcal {S}}}$es un subconjunto de${\displaystyle {\mathcal {C}}}$desde${\displaystyle {\mathcal {S}}}$y${\displaystyle {\mathcal {F}}}$son disjuntos y${\displaystyle {\mathcal {H}}}$son los gráficos mínimos en${\displaystyle {\mathcal {C}}}$Consideremos un gráfico.${\displaystyle G}$en${\displaystyle {\mathcal {H}}}$.${\displaystyle G}$no puede tener un menor adecuado en${\displaystyle {\mathcal {S}}}$desde${\displaystyle G}$es mínimo en${\displaystyle {\mathcal {C}}}$. Al mismo tiempo,${\displaystyle G}$debe tener una especialización menor en${\displaystyle S}$, puesto que de otro modo${\displaystyle G}$sería un elemento en${\displaystyle {\mathcal {F}}}$. Por lo tanto,${\displaystyle G}$es un elemento en${\displaystyle {\mathcal {S}}}$, es decir,${\displaystyle {\mathcal {H}}}$es un subconjunto de${\displaystyle {\mathcal {S}}}$y todos los demás gráficos en${\displaystyle {\mathcal {S}}}$tienen un menor entre los gráficos en${\displaystyle {\mathcal {H}}}$, entonces${\displaystyle {\mathcal {H}}}$es el conjunto finito de elementos mínimos de${\displaystyle {\mathcal {S}}}$.

Para demostrar la otra dirección de la equivalencia, supongamos que cada conjunto de grafos tiene un subconjunto finito de grafos mínimos y sea un conjunto cerrado menor.${\displaystyle {\mathcal {F}}}$ser dado. Queremos encontrar un conjunto${\displaystyle {\mathcal {H}}}$de gráficos de tal manera que un gráfico esté en${\displaystyle {\mathcal {F}}}$si y solo si no tiene un menor en${\displaystyle {\mathcal {H}}}$. Dejar${\displaystyle {\mathcal {E}}}$sean los gráficos que no son menores de ningún gráfico en${\displaystyle {\mathcal {F}}}$y dejar${\displaystyle {\mathcal {H}}}$sea ​​el conjunto finito de grafos mínimos en${\displaystyle {\mathcal {E}}}$Ahora, consideremos un gráfico arbitrario.${\displaystyle G}$ser dado. Supongamos primero que${\displaystyle G}$está en${\displaystyle {\mathcal {F}}}$.${\displaystyle G}$no puede tener un menor en${\displaystyle {\mathcal {H}}}$desde${\displaystyle G}$está en${\displaystyle {\mathcal {F}}}$y${\displaystyle {\mathcal {H}}}$es un subconjunto de${\displaystyle {\mathcal {E}}}$. Ahora supongamos que${\displaystyle G}$no está en${\displaystyle {\mathcal {F}}}$. Entonces${\displaystyle G}$no es un menor de ningún gráfico en${\displaystyle {\mathcal {F}}}$, desde${\displaystyle {\mathcal {F}}}$es menor-cerrado. Por lo tanto,${\displaystyle G}$está en${\displaystyle {\mathcal {E}}}$, entonces${\displaystyle G}$tiene una especialización en${\displaystyle {\mathcal {H}}}$.

Los siguientes conjuntos de grafos finitos son cerrados bajo menores y, por lo tanto (según el teorema de Robertson-Seymour), tienen caracterizaciones menores prohibidas:

• bosques , bosques lineales ( uniones disjuntas de grafos de caminos ), pseudobosques y grafos de cactus ;
• grafos planares , grafos exteriores planares , grafos de vértice (formados al agregar un solo vértice a un grafo planar), grafos toroidales y los grafos que pueden incrustarse en cualquier variedad bidimensional fija ; ^{[ 10 ]}
• grafos que se pueden incrustar sin enlaces en el espacio euclidiano tridimensional, y grafos que se pueden incrustar sin nudos en el espacio euclidiano tridimensional; ^{[ 10 ]}
• grafos con un conjunto de vértices de retroalimentación de tamaño limitado por alguna constante fija; grafos con invariante de grafo de Colin de Verdière limitado por alguna constante fija; grafos con ancho de árbol , ancho de camino o ancho de rama limitados por alguna constante fija.

Algunos ejemplos de conjuntos de obstrucción finitos ya se conocían para clases específicas de grafos antes de que se demostrara el teorema de Robertson-Seymour. Por ejemplo, la obstrucción para el conjunto de todos los bosques es el grafo de bucle (o, si uno se restringe a grafos simples , el ciclo con tres vértices). Esto significa que un grafo es un bosque si y solo si ninguno de sus menores es el bucle (o, el ciclo con tres vértices, respectivamente). La única obstrucción para el conjunto de caminos es el árbol con cuatro vértices, uno de los cuales tiene grado 3. En estos casos, el conjunto de obstrucción contiene un solo elemento, pero en general este no es el caso. El teorema de Wagner establece que un grafo es planar si y solo si no tiene ninguno de los dos${\displaystyle K_{5}}$ni${\displaystyle K_{3,3}}$como menor. En otras palabras, el conjunto${\displaystyle \{K_{5},K_{3,3}\}}$es un conjunto de obstrucciones para el conjunto de todos los grafos planares, y de hecho el único conjunto de obstrucciones mínimo. Un teorema similar establece que${\displaystyle K_{4}}$y${\displaystyle K_{2,3}}$son los menores prohibidos para el conjunto de grafos exteriores planares.

Aunque el teorema de Robertson-Seymour extiende estos resultados a familias de grafos cerradas en menores arbitrarias, no los sustituye por completo, ya que no proporciona una descripción explícita del conjunto de obstrucciones para ninguna familia. Por ejemplo, nos dice que el conjunto de grafos toroidales tiene un conjunto de obstrucciones finito, pero no proporciona dicho conjunto. El conjunto completo de menores prohibidos para grafos toroidales sigue siendo desconocido, pero contiene al menos 17 535 grafos. ^{[ 11 ]}

El teorema de Robertson-Seymour tiene una consecuencia importante en la complejidad computacional, debido a la demostración de Robertson y Seymour de que, para cada grafo fijo${\displaystyle H}$, existe un algoritmo de tiempo polinomial para probar si un grafo tiene${\displaystyle H}$como menor. El tiempo de ejecución de este algoritmo es cúbico (en el tamaño del grafo a comprobar), aunque con un factor constante que depende superpolinómicamente del tamaño del menor.${\displaystyle H}$El tiempo de ejecución ha sido mejorado a cuadrático por Kawarabayashi, Kobayashi y Reed. ^{[ 12 ]} Como resultado, para cada familia cerrada menor${\displaystyle {\mathcal {F}}}$, existe un algoritmo de tiempo polinomial para probar si un grafo pertenece a${\displaystyle {\mathcal {F}}}$: comprobar si el gráfico dado contiene${\displaystyle H}$por cada menor prohibido${\displaystyle H}$en el conjunto de obstrucción de${\displaystyle {\mathcal {F}}}$. ^{[ 13 ]}

Sin embargo, este método requiere un conjunto de obstrucciones finito específico para funcionar, y el teorema no proporciona uno. El teorema prueba que existe tal conjunto de obstrucciones finito y, por lo tanto, el problema es polinomial debido al algoritmo anterior. Sin embargo, el algoritmo puede usarse en la práctica solo si se proporciona dicho conjunto de obstrucciones finito. Como resultado, el teorema prueba que el problema puede resolverse en tiempo polinomial, pero no proporciona un algoritmo concreto de tiempo polinomial para resolverlo. Tales pruebas de polinomio son no constructivas : prueban la polinomioidad de los problemas sin proporcionar un algoritmo explícito de tiempo polinomial. ^{[ 14 ]} En muchos casos específicos, verificar si un grafo está en una familia cerrada de menores dada puede hacerse de manera más eficiente: por ejemplo, verificar si un grafo es planar puede hacerse en tiempo lineal.

Para invariantes de grafos con la propiedad de que, para cada${\displaystyle k}$, los gráficos con invariante como máximo${\displaystyle k}$son cerrados menores, se aplica el mismo método. Por ejemplo, según este resultado, el ancho del árbol, el ancho de la rama y el ancho del camino, la cobertura de vértices y el género mínimo de una incrustación son todos susceptibles a este enfoque, y para cualquier fijo${\displaystyle k}$Existe un algoritmo de tiempo polinomial para probar si estos invariantes son como máximo${\displaystyle k}$, en el que el exponente en el tiempo de ejecución del algoritmo no depende de${\displaystyle k}$Un problema con esta propiedad es que se puede resolver en tiempo polinomial para cualquier fijo.${\displaystyle k}$con un exponente que no depende de${\displaystyle k}$, se conoce como tratable de parámetros fijos .

Sin embargo, este método no proporciona directamente un único algoritmo manejable con parámetros fijos para calcular el valor del parámetro para un gráfico dado con valores desconocidos.${\displaystyle k}$, debido a la dificultad de determinar el conjunto de menores prohibidos. Además, los grandes factores constantes involucrados en estos resultados los hacen altamente imprácticos. Por lo tanto, el desarrollo de algoritmos explícitos de parámetros fijos para estos problemas, con una dependencia mejorada de${\displaystyle k}$, ha seguido siendo una importante línea de investigación.

Friedman , Robertson y Seymour (1987) demostraron que el siguiente teorema exhibe el fenómeno de independencia al ser indemostrable en varios sistemas formales que son mucho más fuertes que la aritmética de Peano , pero ser demostrable en sistemas mucho más débiles que ZFC : ^{[ 15 ]}

Teorema : Para todo entero positivo${\displaystyle n}$, hay un número entero${\displaystyle m}$tan grande que si${\displaystyle G_{1},\dots ,G_{m}}$es una secuencia de grafos finitos no dirigidos, donde cada${\displaystyle G_{i}}$tiene tamaño como máximo${\displaystyle n+i}$, entonces${\displaystyle G_{j}\leq G_{k}}$para algunos${\displaystyle j\leq k}$.

(Aquí, el tamaño de un grafo es el número total de sus vértices y aristas, y ≤ denota el orden menor).

Friedman utiliza este resultado en gráficos subcúbicos simples para construir la función de crecimiento rápido, SSCG . ^{[ 16 ]}

• Teorema de la estructura de grafos

• Bienstock, Daniel; Langston, Michael A. (1995), "Implicaciones algorítmicas del teorema del menor de grafos" (PDF) , Network Models , Handbooks in Operations Research and Management Science, vol.  7, pp. 481–502 , doi : 10.1016/S0927-0507(05)80125-2 , ISBN  978-0-444-89292-8.
• Diestel, Reinhard (2005), "Menores, árboles y WQO", Teoría de grafos ( PDF) (Edición electrónica 2005  ), Springer, pp. 326–367 .
• Fellows, Michael R.; Langston , Michael A. (1988), "Herramientas no constructivas para demostrar la decidibilidad en tiempo polinomial", Journal of the ACM , 35 (3): 727–739 , doi : 10.1145/44483.44491.
• Friedman, Harvey ; Robertson, Neil ; Seymour, Paul (1987), "La metamatemática del teorema del menor de grafos", en Simpson, S. (ed.), Lógica y combinatoria , Matemáticas contemporáneas, vol.  65, Sociedad Matemática Americana , pp. 229–261 .
• Friedman, Harvey (2006). " [ FOM ] 274: Números gráficos subcúbicos" . Departamento de Matemáticas de la Universidad Estatal de Ohio . Archivado del original el 7 de abril de 2024.
• Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke; Reed, Bruce (2012), "El problema de los caminos disjuntos en tiempo cuadrático" (PDF) , Journal of Combinatorial Theory, Serie B , 102 (2): 424–435 , doi : 10.1016/j.jctb.2011.07.004.
• Lovász, László (2005), "Graph Minor Theory", Boletín de la Sociedad Estadounidense de Matemáticas , Nueva Serie, 43 (1): 75– 86, doi : 10.1090/S0273-0979-05-01088-8.
• Myrvold, Wendy ; Woodcock, Jennifer (2018), "Un gran conjunto de obstrucciones toroidales y cómo fueron descubiertas" , The Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236/3797.
• Robertson, Neil ; Seymour, Paul (1983), "Graph Minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B , 35 (1): 39–61 , doi : 10.1016/0095-8956(83)90079-5.
• Robertson, Neil ; Seymour, Paul (1995), "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B , 63 (1): 65–110 , doi : 10.1006/jctb.1995.1006.
• Robertson, Neil ; Seymour, Paul (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B , 92 (2): 325–357 , doi : 10.1016/j.jctb.2004.08.001.

• Weisstein, Eric W. , "Teorema de Robertson-Seymour" , MathWorld