Paul Seymour (matemático) - Paul Seymour (mathematician)

Paul Seymour
PaulSeymour2010.jpg
Nascer ( 1950-07-26 )26 de julho de 1950 (71 anos)
Plymouth , Devon, Inglaterra
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 .

Paul Seymour em 2007
(foto do MFO)

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