Paul Seymour (matemático) - Paul Seymour (mathematician)
Paul Seymour | |
---|---|
Nascer |
Plymouth , Devon, Inglaterra
|
26 de julho de 1950
Nacionalidade | britânico |
Alma mater | Universidade de Oxford (BA, PhD) |
Prêmios |
Sloan Fellowship (1983) Prêmio Ostrowski (2003) Prêmio George Pólya (1983, 2004) Prêmio Fulkerson (1979, 1994, 2006, 2009) |
Carreira científica | |
Instituições |
Princeton University Bellcore University of Waterloo Rutgers University Ohio State University |
Orientador de doutorado | Aubrey William Ingleton |
Alunos de doutorado |
Maria Chudnovsky Sang-il Oum |
Paul D. Seymour (nascido em 26 de julho de 1950) é um matemático britânico conhecido por seu trabalho em matemática discreta , especialmente na teoria dos gráficos . Ele (com outros) foi responsável por importantes progressos em matróides regulares e matrizes totalmente unimodulares , o teorema das quatro cores , embeddings sem links , gráficos menores e estrutura , a conjectura de gráfico perfeito , a conjectura de Hadwiger , gráficos sem garras , delimitação de χ e a conjectura Erdős – Hajnal . Muitos de seus artigos recentes estão disponíveis em seu site.
Seymour é atualmente Professor de Matemática Albert Baldwin Dod na Universidade de Princeton . Ele ganhou uma bolsa Sloan em 1983 e o Prêmio Ostrowski em 2004; e (às vezes com outros) ganhou o Prêmio Fulkerson em 1979, 1994, 2006 e 2009, e o Prêmio Pólya em 1983 e 2004. Ele recebeu um doutorado honorário da Universidade de Waterloo em 2008 e um da Universidade Técnica da Dinamarca em 2013 Foi orador convidado no Congresso Internacional de Matemáticos de 1986 e orador plenário no Congresso Internacional de Matemáticos de 1994 .
Vida pregressa
Seymour nasceu em Plymouth , Devon, Inglaterra. Ele foi um aluno do Plymouth College e, em seguida, estudou no Exeter College, Oxford , obtendo um diploma de bacharelado em 1971 e D.Phil em 1975.
Carreira
De 1974 a 1976, ele foi bolsista de pesquisa universitária na University College of Swansea e, em seguida, retornou a Oxford em 1976–1980 como Pesquisador Júnior no Merton College, Oxford , no ano de 1978–79 na University of Waterloo . Tornou-se associado e professor titular na Ohio State University , Columbus, Ohio , entre 1980 e 1983, onde começou a pesquisar com Neil Robertson , uma colaboração frutífera que continuou por muitos anos. De 1983 a 1996, ele trabalhou na Bellcore (Bell Communications Research), Morristown, New Jersey (agora Telcordia Technologies ). Ele também foi professor adjunto na Rutgers University de 1984 a 1987 e na University of Waterloo de 1988 a 1993. Ele se tornou professor da Princeton University em 1996. Ele é Editor-Chefe (juntamente com Carsten Thomassen ) do Journal of Teoria dos Grafos , e um editor para Combinatorica eo Journal of Teoria Combinatória, Série B .
Vida pessoal
Ele se casou com Shelley MacDonald de Ottawa em 1979, e eles têm dois filhos, Amy e Emily. O casal se separou amigavelmente em 2007. Seu irmão Leonard W. Seymour é professor de terapia genética na Universidade de Oxford .
Principais contribuições
A Combinatória em Oxford na década de 1970 foi dominada pela teoria matróide , devido à influência de Dominic Welsh e Aubrey William Ingleton . Muito do trabalho inicial de Seymour, até cerca de 1980, foi sobre a teoria dos matróides e incluiu três resultados importantes dos matróides: seu D.Phil. tese sobre matróides com a propriedade de corte mínimo de fluxo máximo (pela qual ganhou seu primeiro prêmio Fulkerson); uma caracterização por menores excluídos das matróides representáveis no campo de três elementos; e um teorema de que todas as matróides regulares consistem em matróides gráficas e cográficas reunidas de uma maneira simples (que ganhou seu primeiro prêmio Pólya). Houve vários outros artigos importantes desse período: um artigo com Welsh sobre as probabilidades críticas de percolação de títulos na rede quadrada; artigo em que foi introduzida a conjectura de dupla capa do ciclo ; um artigo sobre a multicor de bordas de gráficos cúbicos, que prenuncia o teorema da rede de correspondência de László Lovász ; um artigo provando que todos os gráficos sem ponte admitem fluxos em lugar nenhum-zero 6, um passo em direção à conjectura de 5 fluxos em lugar nenhum-zero de Tutte ; e um artigo resolvendo o problema dos dois caminhos, que foi o motor por trás de grande parte do trabalho futuro de Seymour.
Em 1980 mudou-se para a Ohio State University e começou a trabalhar com Neil Robertson. Isso acabou levando à realização mais importante de Seymour, o chamado "Projeto de menores de grafos", uma série de 23 artigos (em conjunto com Robertson), publicados nos próximos trinta anos, com vários resultados significativos: o teorema da estrutura de menores de grafos , que para qualquer grafo fixo, todos os grafos que não o contenham como um menor podem ser construídos a partir de grafos que são essencialmente de gênero limitado, juntando-os em pequenos conjuntos de cortes em uma estrutura de árvore; uma prova de uma conjectura de Wagner de que em qualquer conjunto infinito de grafos, um deles é menor do outro (e conseqüentemente que qualquer propriedade de grafos que pode ser caracterizada por menores excluídos pode ser caracterizada por uma lista finita de menores excluídos); uma prova de uma conjectura semelhante de Nash-Williams de que em qualquer conjunto infinito de gráficos, um deles pode estar imerso em outro; e algoritmos de tempo polinomial para testar se um grafo contém um grafo fixo como menor, e para resolver o problema de k caminhos disjuntos do vértice para todos os k fixos.
Por volta de 1990, Robin Thomas começou a trabalhar com Robertson e Seymour. A colaboração deles resultou em vários documentos conjuntos importantes ao longo dos próximos dez anos: uma prova de uma conjectura de Sachs , caracterizando por menores excluídos os gráficos que admitem embeddings sem links em 3-espaço; uma prova de que todo gráfico que não seja de cinco cores tem um gráfico completo de seis vértices como menor (presume-se que o teorema de quatro cores obtenha esse resultado, que é um caso da conjectura de Hadwiger ); com Dan Sanders, uma nova prova simplificada e baseada em computador do teorema das quatro cores ; e uma descrição dos grafos bipartidos que admitem orientações Pfaffianas . No mesmo período, Seymour e Thomas também publicaram vários resultados significativos: (com Noga Alon ) um teorema do separador para grafos com um menor excluído, estendendo o teorema do separador planar de Richard Lipton e Robert Tarjan ; um papel que caracteriza a largura da árvore em termos de amoreiras ; e um algoritmo de tempo polinomial para calcular a largura do ramo de gráficos planares.
Em 2000, Robertson, Seymour e Thomas foram apoiados pelo American Institute of Mathematics para trabalhar na conjectura do gráfico perfeito forte , uma famosa questão em aberto que foi levantada por Claude Berge no início dos anos 1960. A aluna de Seymour, Maria Chudnovsky, juntou-se a eles em 2001 e, em 2002, os quatro juntos provaram a conjectura. Seymour continuou a trabalhar com Chudnovsky e obteve vários outros resultados sobre subgráficos induzidos, em particular (com Cornuéjols , Liu, Vuskovic) um algoritmo de tempo polinomial para testar se um gráfico é perfeito e uma descrição geral de todos os gráficos livres de garras. Outros resultados importantes neste período incluem: (com o aluno de Seymour Sang-il Oum ) algoritmos tratáveis de parâmetros fixos para aproximar a largura do clique dos gráficos (dentro de um limite exponencial) e a largura do ramo dos matróides (dentro de um limite linear); e (com Chudnovsky) uma prova de que as raízes do polinômio de independência de cada gráfico livre de garras são reais.
Na década de 2010, Seymour trabalhou principalmente no χ-bounded e na conjectura Erdős-Hajnal . Em uma série de artigos com Alex Scott e parcialmente com Chudnovsky, eles provaram duas conjecturas de András Gyárfás , que todo gráfico com número de clique limitado e número cromático suficientemente grande tem um ciclo induzido de comprimento ímpar de pelo menos cinco, e tem um ciclo induzido de comprimento pelo menos qualquer número especificado. A série culminou em um artigo de Scott e Seymour provando que para cada k fixo, todo gráfico com número cromático suficientemente grande contém um grande subgrafo completo ou ciclos induzidos de todos os comprimentos módulo k, o que leva à resolução de duas conjecturas de Gil Kalai e Roy Meshulam conectando o número cromático de um gráfico com a homologia de seu complexo de independência . Havia também um algoritmo de tempo polinomial (com Chudnovsky, Scott e Chudnovsky e a aluna de Seymour, Sophie Spirkl) para testar se um gráfico contém um ciclo induzido com comprimento maior que três e ímpar. Mais recentemente, os quatro resolveram em conjunto o caso de 5 ciclos da conjectura Erdős-Hajnal, que diz que todo grafo sem uma cópia induzida do 5 ciclos contém um conjunto independente ou um clique de tamanho polinomial.
Veja também
Referências
links externos
- Página inicial de Paul Seymour na Universidade de Princeton
- Paul Seymour no Mathematics Genealogy Project