Paul D. Seymour (nacido el 26 de julio de 1950) es un matemático británico conocido por su trabajo en matemáticas discretas , especialmente en teoría de grafos . Él (con otros) fue responsable de importantes avances en matroides regulares y matrices totalmente unimodulares , el teorema de los cuatro colores , incrustaciones sin enlaces , los menores de gráficos y la estructura , la gráfica perfecta conjetura, la conjetura de Hadwiger , gráficos sin garra , χ-acotación , y la conjetura de Erdős-Hajnal . Muchos de sus artículos recientes están disponibles en su sitio web.[1]
Paul Seymour | |
---|---|
Nació | Plymouth , Devon, Inglaterra | 26 de julio de 1950
Nacionalidad | británico |
alma mater | Universidad de Oxford (BA, PhD) |
Premios | Beca Sloan (1983) Premio Ostrowski (2003) Premio George Pólya (1983, 2004) Premio Fulkerson (1979, 1994, 2006, 2009) |
Carrera científica | |
Instituciones | Universidad de Princeton Universidad Bellcore de Waterloo Universidad Rutgers Universidad Estatal de Ohio |
Asesor de doctorado | Aubrey William Ingleton |
Estudiantes de doctorado | Maria Chudnovsky Sang-il Oum |
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 2004; 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 honoris causa de la Universidad de Waterloo en 2008 y uno de la Universidad Técnica de Dinamarca en 2013 Fue orador invitado en el Congreso Internacional de Matemáticos de 1986 y orador plenario en el Congreso Internacional de Matemáticos de 1994 .
Vida temprana
Seymour nació en Plymouth , Devon, Inglaterra. Era un estudiante de día en Plymouth Colegio , y luego estudió en la universidad de Exeter, Oxford , ganando un BA grado en 1971, y D. Phil en 1975.
Carrera profesional
De 1974 a 1976 fue investigador universitario en la University College of Swansea , y luego regresó a Oxford durante 1976-1980 como investigador junior en Merton College, Oxford , con el año 1978-79 en la Universidad de Waterloo . Se convirtió en asociado y luego en 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 en la Universidad de Princeton en 1996. Es editor en jefe (junto con Carsten Thomassen ) del Journal of teoría de grafos , y un editor para Combinatorica y la Revista de Teoría combinatoria, Serie B .
Vida personal
Se casó con Shelley MacDonald de Ottawa en 1979 y tienen dos hijos, Amy y Emily. La pareja se separó amistosamente en 2007. Su hermano Leonard W. Seymour es profesor de terapia génica en la Universidad de Oxford . [3]
Contribuciones importantes
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 del trabajo inicial de Seymour, hasta aproximadamente 1980, se centró en la teoría matroide e incluyó tres resultados importantes de la matroide: su D.Phil. tesis sobre matroides con la propiedad max-flow min-cut (por la que ganó su primer premio Fulkerson); una caracterización por los menores excluidos de las matroides representables en el campo de los tres elementos; y un teorema de que todas las matroides regulares consisten en matroides gráficas y cográficas ensambladas de una manera simple (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 la percolación de enlaces en la red cuadrada; un trabajo en el que se introdujo la conjetura del ciclo de doble portada ; un artículo sobre el multicolores de bordes de gráficos cúbicos, que presagia el teorema de celosía coincidente de László Lovász ; un artículo que demuestra que todas las gráficas sin puentes admiten flujos 6 en ninguna parte, cero, un paso hacia la conjetura de flujo 5 en ninguna parte cero de Tutte ; y un documento que resuelve el problema de los dos caminos, que fue el motor detrás de gran parte del trabajo futuro de Seymour.
En 1980 se mudó 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 "Graph Minors Project", una serie de 23 artículos (en conjunto con Robertson), publicados durante los siguientes treinta años, con varios resultados significativos: el teorema de la estructura del grafo menor , 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; 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); una prueba de una conjetura similar de Nash-Williams de que en cualquier conjunto infinito de gráficos, uno de ellos puede sumergirse en otro; y algoritmos de tiempo polinomial para probar si una gráfica contiene una gráfica fija como menor, y para resolver el problema de k trayectorias disjuntas de vértice para todas las k fijas.
Aproximadamente en 1990, Robin Thomas comenzó a trabajar con Robertson y Seymour. Su colaboración resultó en varios artículos conjuntos importantes durante los próximos diez años: una prueba de una conjetura de Sachs , caracterizando por menores excluidos los gráficos que admiten incrustaciones sin enlaces en 3 espacios; una prueba de que todo gráfico que no sea de 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 ); con Dan Sanders, una nueva prueba simplificada basada en computadora del teorema de los cuatro colores ; y una descripción de los gráficos bipartitos que admiten orientaciones pfaffianas . 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, ampliando el teorema del separador plano de Richard Lipton y Robert Tarjan ; un documento que caracteriza el ancho de los árboles en términos de zarzas ; y un algoritmo de tiempo polinomial para calcular el ancho de rama de los gráficos planos.
En 2000, Robertson, Seymour y Thomas recibieron el apoyo del Instituto Americano de Matemáticas para trabajar en la conjetura de la gráfica perfecta fuerte , una famosa pregunta abierta que había planteado Claude Berge a principios de la década de 1960. La estudiante de Seymour, Maria Chudnovsky, se unió a ellos en 2001, y en 2002 los cuatro probaron conjuntamente la conjetura. Seymour continuó trabajando con Chudnovsky y obtuvo varios resultados más sobre subgrafos inducidos, en particular (con Cornuéjols , Liu, Vuskovic) un algoritmo de tiempo polinomial para probar si un gráfico es perfecto y una descripción general de todos los gráficos sin garras. 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 la camarilla de los gráficos (dentro de un límite exponencial) y el ancho de rama de las matroides (dentro de un límite lineal); y (con Chudnovsky) una prueba de que las raíces del polinomio de independencia de cada grafo sin garras son reales.
En la década de 2010, Seymour trabajó principalmente en los límites χ 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 todo gráfico con un número de clique acotado y un número cromático suficientemente grande tiene un ciclo inducido de duración impar de al menos cinco, y tiene un ciclo inducido de longitud al menos cualquier número especificado. La serie culminó con un artículo de Scott y Seymour que demostró 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, lo que conduce a las resoluciones de dos conjeturas de Gil Kalai y Roy Meshulam conectando el número cromático de un gráfico con la homología de su complejo de independencia . También había un algoritmo de tiempo polinomial (con Chudnovsky, Scott y Chudnovsky y la estudiante de Seymour, Sophie Spirkl) para probar si una gráfica contiene un ciclo inducido con una longitud de más de tres e impar. 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 de los 5 ciclos contiene un conjunto independiente o una camarilla de tamaño polinómico.
Ver también
- Teorema de Robertson-Seymour
- Teorema del grafo perfecto fuerte
Referencias
- ^ Seymour, Paul. "Documentos en línea" . Consultado el 26 de abril de 2013 .
- ^ https://dof.princeton.edu/about/faculty/professorships
- ^ http://news.bbc.co.uk/1/hi/health/6251303.stm
enlaces externos
- Página de inicio de Paul Seymour en la Universidad de Princeton
- Paul Seymour en el Proyecto de genealogía matemática