Paul D. Seymour FRS (nacido el 26 de julio de 1950) es un matemático británico conocido por su trabajo en matemáticas discretas , especialmente teoría de grafos . Él (junto con otros) fue responsable de importantes avances en matroides regulares y matrices totalmente unimodulares , el teorema de los cuatro colores , incrustaciones sin enlaces , menores y estructura de grafos , la conjetura del grafo perfecto , la conjetura de Hadwiger , grafos sin garras , acotación χ y la conjetura de Erdős-Hajnal . Muchos de sus artículos recientes están disponibles en su sitio web. [1]
Seymour es actualmente profesor de matemáticas Albert Baldwin Dod en la Universidad de Princeton . [2] Ganó una beca Sloan en 1983 y el premio Ostrowski en 2003; [3] y (a veces con otros) ganó el premio Fulkerson en 1979, 1994, 2006 y 2009, y el premio Pólya en 1983 y 2004. Recibió un doctorado honorario de la Universidad de Waterloo en 2008, uno de la Universidad Técnica de Dinamarca en 2013 y uno de la École normale supérieure de Lyon en 2022. Fue orador invitado en el Congreso Internacional de Matemáticos de 1986 y orador plenario en el Congreso Internacional de Matemáticos de 1994. Se convirtió en miembro de la Royal Society en 2022. [4]
Seymour nació en Plymouth , Devon, Inglaterra. Fue alumno externo en el Plymouth College y luego estudió en el Exeter College de Oxford , donde obtuvo una licenciatura en 1971 y un doctorado en 1975.
De 1974 a 1976 fue investigador universitario en el University College de Swansea , y luego regresó a Oxford para 1976-1980 como investigador junior en el Merton College, Oxford , con el año 1978-79 en la Universidad de Waterloo . [5] Se convirtió en asociado y luego profesor titular en la Universidad Estatal de Ohio , Columbus, Ohio , entre 1980 y 1983, donde comenzó a investigar con Neil Robertson , una fructífera colaboración que continuó durante muchos años. Desde 1983 hasta 1996, estuvo en Bellcore (Bell Communications Research), Morristown, Nueva Jersey (ahora Telcordia Technologies ). También fue profesor adjunto en la Universidad Rutgers de 1984 a 1987 y en la Universidad de Waterloo de 1988 a 1993. Se convirtió en profesor en la Universidad de Princeton en 1996. [5] Es editor en jefe (junto con Carsten Thomassen ) del Journal of Graph Theory , [6] y editor de Combinatorica [7] y del Journal of Combinatorial Theory, Serie B. [8 ]
Se casó con Shelley MacDonald de Ottawa en 1979 y tienen dos hijos, Amy y Emily. La pareja se separó amistosamente en 2007. [ cita requerida ] Su hermano Leonard W. Seymour es profesor de terapia genética en la Universidad de Oxford . [ 9 ]
La combinatoria en Oxford en la década de 1970 estaba dominada por la teoría de matroides , debido a la influencia de Dominic Welsh y Aubrey William Ingleton . Gran parte del trabajo temprano de Seymour, hasta aproximadamente 1980, fue sobre la teoría de matroides, e incluyó tres resultados importantes sobre matroides: su tesis de doctorado sobre matroides con la propiedad de flujo máximo y corte mínimo [pub 1] (por la que ganó su primer premio Fulkerson); una caracterización por menores excluidos de los matroides representables sobre el cuerpo de tres elementos; [pub 2] y un teorema de que todos los matroides regulares consisten en matroides gráficos y cográficos unidos de una manera simple [pub 3] (que ganó su primer premio Pólya). Hubo varios otros artículos importantes de este período: un artículo con Welsh sobre las probabilidades críticas para la percolación de enlaces en la red cuadrada; [pub 4] un artículo sobre la multicolorización de los bordes de los grafos cúbicos, [pub 5] que anticipa el teorema de red correspondiente de László Lovász ; un artículo que demuestra que todos los grafos sin puente admiten 6-flujos de cero en ninguna parte, [pub 6] un paso hacia la conjetura de 5-flujos de cero en ninguna parte de Tutte ; y un artículo que resuelve el problema de los dos caminos (que también introduce la conjetura de doble cobertura del ciclo ), [pub 7] que fue el motor detrás de gran parte del trabajo futuro de Seymour.
En 1980 se trasladó a la Universidad Estatal de Ohio y comenzó a trabajar con Neil Robertson. Esto condujo finalmente al logro más importante de Seymour, el llamado "Proyecto de los menores de grafos", una serie de 23 artículos (junto con Robertson), publicados durante los siguientes treinta años, con varios resultados significativos: el teorema de la estructura de los menores de grafos , que para cualquier grafo fijo, todos los grafos que no lo contienen como menor pueden construirse a partir de grafos que son esencialmente de género acotado uniéndolos en pequeños conjuntos de corte en una estructura de árbol; [pub 8] una prueba de una conjetura de Wagner de que en cualquier conjunto infinito de grafos, uno de ellos es un menor de otro (y en consecuencia que cualquier propiedad de los grafos que puede caracterizarse por menores excluidos puede caracterizarse por una lista finita de menores excluidos); [pub 9] una prueba de una conjetura similar de Nash-Williams de que en cualquier conjunto infinito de grafos, uno de ellos puede estar inmerso en otro; [pub 10] y algoritmos de tiempo polinomial para probar si un gráfico contiene un gráfico fijo como menor, y para resolver el problema de k caminos disjuntos en los vértices para todos los k fijos. [pub 11]
En 1990, Robin Thomas comenzó a trabajar con Robertson y Seymour. Su colaboración dio como resultado varios artículos conjuntos importantes durante los siguientes diez años: una prueba de una conjetura de Sachs , que caracteriza por menores excluidos los grafos que admiten incrustaciones sin enlaces en el espacio tridimensional; [pub 12] una prueba de que todo grafo que no es de cinco colores tiene un grafo completo de seis vértices como menor (se supone que el teorema de los cuatro colores obtiene este resultado, lo que es un caso de la conjetura de Hadwiger ); [pub 13] con Dan Sanders , una nueva prueba simplificada basada en computadora del teorema de los cuatro colores ; [pub 14] y una descripción de los grafos bipartitos que admiten orientaciones pfaffianas . [pub 15] En el mismo período, Seymour y Thomas también publicaron varios resultados significativos: (con Noga Alon ) un teorema separador para gráficos con un menor excluido, [pub 16] extendiendo el teorema separador planar de Richard Lipton y Robert Tarjan ; un artículo que caracteriza el ancho de los árboles en términos de zarzas ; [pub 17] y un algoritmo de tiempo polinomial para calcular el ancho de las ramas de gráficos planares. [pub 18]
En 2000, Robertson, Seymour y Thomas recibieron apoyo del Instituto Americano de Matemáticas para trabajar en la conjetura del grafo perfecto fuerte , una famosa cuestión abierta que había sido planteada por Claude Berge a principios de los años 1960. La estudiante de Seymour, Maria Chudnovsky, se unió a ellos en 2001, y en 2002 los cuatro demostraron conjuntamente la conjetura. [pub 19] Seymour continuó trabajando con Chudnovsky y obtuvo varios resultados más sobre subgrafos inducidos, en particular (con Cornuéjols , Liu y Vušković ) un algoritmo de tiempo polinomial para probar si un grafo es perfecto, [pub 20] y una descripción general de todos los grafos sin garras. [pub 21] Otros resultados importantes en este período incluyen: (con el estudiante de Seymour Sang-il Oum ) algoritmos manejables con parámetros fijos para aproximar el ancho de camarilla de los gráficos (dentro de un límite exponencial) y el ancho de rama de los matroides (dentro de un límite lineal); [pub 22] y (con Chudnovsky) una prueba de que las raíces del polinomio de independencia de cada gráfico sin garras son reales. [pub 23]
En la década de 2010, Seymour trabajó principalmente en la acotación de χ y la conjetura de Erdős–Hajnal . En una serie de artículos con Alex Scott y en parte con Chudnovsky, demostraron dos conjeturas de András Gyárfás , que cada grafo con un número de clique acotado y un número cromático suficientemente grande tiene un ciclo inducido de longitud impar de al menos cinco, [pub 24] y tiene un ciclo inducido de longitud de al menos cualquier número especificado. [pub 25] La serie culminó en un artículo de Scott y Seymour que demuestra que para cada k fijo, cada grafo con un número cromático suficientemente grande contiene un subgrafo completo grande o ciclos inducidos de todas las longitudes módulo k, [pub 26] lo que conduce a las resoluciones de dos conjeturas de Gil Kalai y Roy Meshulam que conectan el número cromático de un grafo con la homología de su complejo de independencia . También hubo un algoritmo de tiempo polinomial (con Chudnovsky, Scott y Chudnovsky y la estudiante de Seymour, Sophie Spirkl) para probar si un gráfico contiene un ciclo inducido con una longitud mayor que tres e impar. [pub 27] Más recientemente, los cuatro resolvieron conjuntamente el caso de 5 ciclos de la conjetura de Erdős-Hajnal, que dice que cada gráfico sin una copia inducida del 5-ciclo contiene un conjunto independiente o una camarilla de tamaño polinomial. [pub 28]
