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 , grafos menores y estructura , la conjetura del grafo perfecto , la conjetura de Hadwiger , grafos sin garras , acotación de χ 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 estudiante diurno en Plymouth College y luego estudió en Exeter College, Oxford , donde obtuvo una licenciatura en 1971 y un doctorado en filosofía en 1975.
De 1974 a 1976 fue investigador universitario en el University College of Swansea , y luego regresó a Oxford para 1976-1980 como investigador junior en Merton College, Oxford , y 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 de Rutgers de 1984 a 1987 y en la Universidad de Waterloo de 1988 a 1993. Se convirtió en profesor de la Universidad de Princeton en 1996. [5] Es editor en jefe (junto con Carsten Thomassen ) de el Journal of Graph Theory , [6] y editor de Combinatorica [7] y el 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 necesaria ] Su hermano Leonard W. Seymour es profesor de terapia génica en la Universidad de Oxford . [9]
La combinatoria en Oxford en la década de 1970 estuvo dominada por la teoría matroide , debido a la influencia de Dominic Welsh y Aubrey William Ingleton . Gran parte de los primeros trabajos de Seymour, hasta aproximadamente 1980, se centraron en la teoría de las matroides e incluyeron tres resultados importantes de las matroides: su D.Phil. tesis sobre matroides con la propiedad max-flow min-cut [pub 1] (por la que ganó su primer premio Fulkerson); una caracterización por menores excluidos de las matroides representables sobre el campo de los tres elementos; [pub 2] y un teorema de que todas las matroides regulares consisten en matroides gráficas y cográficas ensambladas de una manera sencilla [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 de percolación de bonos en la red cuadrada; [pub 4] un artículo sobre la coloración de bordes de gráficos cúbicos, [pub 5] que presagia el teorema de red coincidente de László Lovász ; un artículo que demuestra que todos los gráficos sin puentes admiten 6 flujos en ninguna parte cero, [pub 6] un paso hacia la conjetura de 5 flujos en ninguna parte cero de Tutte ; y un artículo que resuelve el problema de los dos caminos (que también presenta la conjetura de la 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 llevó finalmente al logro más importante de Seymour, el llamado "Proyecto Graph Minors", 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 grafos menores , que para cualquier gráfico fijo, todos los gráficos que no lo contienen como menor, se pueden construir a partir de gráficos que son esencialmente de género acotado uniéndolos en pequeños cortes en una estructura de árbol; [pub 8] una prueba de una conjetura de Wagner de que en cualquier conjunto infinito de gráficos, uno de ellos es menor de otro (y, en consecuencia, que cualquier propiedad de los gráficos que pueda 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 gráficos, uno de ellos puede estar sumergido 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 de vértices para todos los k fijos. [publicación 11]
Aproximadamente en 1990 , Robin Thomas comenzó a trabajar con Robertson y Seymour. Su colaboración resultó en varios artículos conjuntos importantes durante los siguientes diez años: una prueba de una conjetura de Sachs , caracterizando por menores excluidos los grafos que admiten incrustaciones sin enlaces en 3 espacios; [pub 12] una prueba de que todo gráfico que no tiene cinco colores tiene un gráfico completo de seis vértices como menor (se supone que el teorema de los cuatro colores obtiene este resultado, que es un caso de la conjetura de Hadwiger ); [pub 13] con Dan Sanders , una prueba nueva, simplificada y basada en computadora del teorema de los cuatro colores ; [pub 14] y una descripción de los gráficos 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 del separador para gráficos con un menor excluido, [pub 16] extendiendo el teorema del separador plano 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 rama de gráficos planos. [publicación 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 pregunta abierta que había planteado Claude Berge a principios de la década de 1960. La alumna de Seymour, María 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 gráfico es perfecto, [pub 20] y un Descripción general de todos los gráficos sin garras. [pub 21] Otros resultados importantes en este período incluyen: (con el estudiante de Seymour, Sang-il Oum ) algoritmos manejables de parámetros fijos para aproximar el ancho de camarilla de gráficos (dentro de un límite exponencial) y el ancho de rama de 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. [publicación 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 gráfico con un número de camarilla acotado y un número cromático suficientemente grande tiene un ciclo inducido de longitud impar al menos cinco, [pub 24] y tiene un ciclo inducido de longitud 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 gráfico 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 superior a 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 ciclo de 5 contiene un conjunto independiente o una camarilla de tamaño polinómico. [publicación 28]
