Paul D. Seymour (nascido em 1950) é um matemático britânico conhecido por seu trabalho em matemática discreta, especialmente teoria dos grafos. Ele (com outros) foi responsável por avanços importantes em matroides regulares e matrizes totalmente unimodulares, o teorema das quatro cores, incorporação sem eloss, menores e estrutura de grafos, a conjectura do grafo perfeito, a conjectura de Hadwiger, grafos sem garras, χ-limitação e a conjectura de Erdős–Hajnal. Muitos de seus artigos recentes estão disponíveis em seu site.
Seymour é atualmente o Professor Albert Baldwin Dod de Matemática na Universidade de Princeton. Ele ganhou uma Bolsa Sloan em 1983 e o Prêmio Ostrowski em 2003; 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, um da Universidade Técnica da Dinamarca em 2013 e um da Escola Normal Superior de Lyon em 2022. Ele foi palestrante convidado no Congresso Internacional de Matemáticos de 1986 e palestrante plenário no Congresso Internacional de Matemáticos de 1994. Tornou-se membro da Royal Society em 2022.
Seymour nasceu em Plymouth, Inglaterra, em 1950. Seymour foi aluno do Plymouth College, e depois estudou no Exeter College, Oxford, obtendo um diploma de BA em 1971, um diploma de MS em 1972 e D.Phil e MA em 1975. Sua dissertação de doutorado, Matroids, Hypergraphs and the Max-Flow Min-Cut Theorem, foi orientada por Aubrey William Ingleton.
De 1974 a 1976, ele foi pesquisador universitário no University College of Swansea. Em seguida, retornou a Oxford para o período de 1976–1980 como Pesquisador Júnior no Merton College, Oxford, com o ano de 1978–79 na Universidade de Waterloo. Tornou-se professor associado e depois professor titular na Universidade Estadual de Ohio, em Columbus, Ohio, entre 1980 e 1983, onde iniciou uma pesquisa com Neil Robertson, uma colaboração frutífera que continuou por muitos anos. De 1983 até 1996, foi cientista sênior na Bellcore (Bell Communications Research), em Morristown, Nova Jérsei (atualmente Telcordia Technologies). Também foi professor adjunto na Universidade Rutgers de 1984 a 1987 e na Universidade de Waterloo de 1988 a 1993. Tornou-se professor na Universidade de Princeton em 1996. Em Princeton, recebeu a Cátedra Albert Baldwin Dod em 2016.
Ele é Editor-Chefe (juntamente com Carsten Thomassen) do Journal of Graph Theory, e editor do Combinatorica e do Journal of Combinatorial Theory, Series B.
O irmão de Seymour, Leonard W. Seymour, é Professor de terapia gênica na Universidade de Oxford. Em 1979, Seymour se casou e teve dois filhos.
A combinatória em Oxford na década de 1970 foi dominada pela teoria dos matroides, devido à influência de Dominic Welsh e Aubrey William Ingleton. Grande parte do trabalho inicial de Seymour, até cerca de 1980, foi sobre teoria dos matroides e incluiu três resultados importantes sobre matroides: sua tese de D.Phil. sobre matroides com a propriedade de fluxo máximo-corte mínimo (pela qual ganhou seu primeiro prêmio Fulkerson); uma caracterização por menores excluídos dos matroides representáveis sobre o corpo de três elementos; e um teorema de que todos os matroides regulares consistem em matroides gráficos e cográficos, e um matroide especial chamado R10, unidos de maneira simples (o que lhe rendeu seu primeiro prêmio Pólya). Houve vários outros artigos significativos desse período: um artigo com Welsh sobre as probabilidades críticas para a percolação de ligações na rede quadrada; um artigo sobre multicoloracão de arestas de grafos cúbicos, que prenuncia o teorema do reticulado de emparelhamentos de László Lovász; um artigo provando que todos os grafos sem pontes admitem fluxos 6 sem zeros, um passo em direção à conjectura do fluxo 5 sem zeros de Tutte; e um artigo resolvendo o problema dos dois caminhos (também introduzindo a conjectura do duplo ciclo), que foi o motor por trás de grande parte do trabalho futuro de Seymour.
Em 1980, mudou-se para a Universidade Estadual de Ohio e começou a trabalhar com Neil Robertson. Isso levou eventualmente à realização mais importante de Seymour, o chamado "Projeto Menores de Grafos", uma série de 23 artigos (em conjunto com Robertson), publicados ao longo dos trinta anos seguintes, com vários resultados significativos: o teorema da estrutura de menores de grafos, de que para qualquer grafo fixo, todos os grafos que não o contêm como menor podem ser construídos a partir de grafos que são essencialmente de gênero limitado, unindo-os em cortes pequenos em uma estrutura de árvore; uma prova de uma conjectura de Wagner de que em qualquer conjunto infinito de grafos, um deles é menor de outro (e consequentemente 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 grafos, um deles pode ser 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 dos k caminhos disjuntos em vértices para todo k fixo.
Por volta de 1990, Robin Thomas começou a trabalhar com Robertson e Seymour. Sua colaboração resultou em vários artigos conjuntos importantes nos dez anos seguintes: uma prova de uma conjectura de Sachs, caracterizando por menores excluídos os grafos que admitem incorporação sem elos no espaço tridimensional; uma prova de que todo grafo que não é cinco-colorível tem um grafo completo de seis vértices como menor (o teorema das quatro cores é assumido para obter esse resultado, que é um caso da conjectura de Hadwiger); com Dan Sanders, uma nova prova simplificada, 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 separador para grafos com um menor excluído, estendendo o teorema separador planar de Richard Lipton e Robert Tarjan; um artigo caracterizando a largura arbórea em termos de brambles; e um algoritmo de tempo polinomial para calcular a largura de ramo de grafos planares.
Em 2000, Robertson, Seymour e Thomas foram apoiados pelo Instituto Americano de Matemática para trabalhar na conjectura do grafo perfeito forte, uma famosa questão em aberto que havia sido 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 provaram conjuntamente a conjectura. Seymour continuou a trabalhar com Chudnovsky e obteve vários outros resultados sobre subgrafos induzidos, em particular (com Cornuéjols, Liu e Vušković) um algoritmo de tempo polinomial para testar se um grafo é perfeito, e uma descrição geral de todos os grafos sem garras. Outros resultados importantes nesse período incluem: (com o aluno de Seymour, Sang-il Oum) algoritmos tratáveis por parâmetro fixo para aproximar a largura de clique de grafos (dentro de um limite exponencial) e a largura de ramo de matroides (dentro de um limite linear); e (com Chudnovsky) uma prova de que as raízes do polinômio de independência de todo grafo sem garras são reais.
Na década de 2010, Seymour trabalhou principalmente em χ-limitação e na conjectura de Erdős–Hajnal. Em uma série de artigos com Alex Scott e, em parte, com Chudnovsky, eles provaram duas conjecturas de András Gyárfás: que todo grafo 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 que 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 todo k fixo, todo grafo com número cromático suficientemente grande contém um subgrafo completo grande ou ciclos induzidos de todos os comprimentos módulo k, o que leva às resoluções de duas conjecturas de Gil Kalai e Roy Meshulam conectando o número cromático de um grafo com a homologia de seu complexo de independência. Houve também um algoritmo de tempo polinomial (com Chudnovsky, Scott, e a aluna de Chudnovsky e Seymour, Sophie Spirkl) para testar se um grafo contém um ciclo induzido com comprimento maior que três e ímpar. Mais recentemente, os quatro resolveram conjuntamente o caso do ciclo de comprimento 5 da conjectura de Erdős–Hajnal, que diz que todo grafo sem uma cópia induzida do ciclo de comprimento 5 contém um conjunto independente ou um clique de tamanho polinomial.