Paul Seymour (mathematician)

Seymour was a student at Plymouth College,{{cite web|url=https://www.plymouthcollege.com/information/about-plymouth-college|work=About Plymouth College|title=Plymouth College Alumni Leaders and Champions|access-date=2025-03-07}} and then studied at Exeter College, Oxford, gaining a BA degree in 1971, and D.Phil in 1975. His doctoral dissertation, Matroids, Hypergraphs and the Max-Flow Min-Cut Theorem, was supervised by Aubrey William Ingleton.{{mathgenealogy|50728}}

From 1974 to 1976 he was a college research fellow at University College of Swansea, and then returned to Oxford for 1976–1980 as a Junior Research Fellow at Merton College, Oxford, with the year 1978–79 at University of Waterloo.{{cite web|title=Paul Seymour's CV

|url=https://web.math.princeton.edu/~pds/papers/vita/vita.pdf|access-date=27 May 2022}} He became an associate and then a full professor at Ohio State University, Columbus, Ohio, between 1980 and 1983, where he began research with Neil Robertson,

a fruitful collaboration that continued for many years. From 1983 until 1996, he was at Bellcore (Bell Communications Research), Morristown, New Jersey (now Telcordia Technologies). He was also an adjunct professor at Rutgers University from 1984 to 1987 and at the University of Waterloo from 1988 to 1993. He became professor at Princeton University in 1996.{{cite web|title=Paul Seymour's CV

|url=https://web.math.princeton.edu/~pds/papers/vita/vita.pdf|access-date=27 May 2022}} He is Editor-in-Chief (jointly with Carsten Thomassen) for the Journal of Graph Theory,{{cite web|title=Journal of Graph Theory Editorial Board

|url=https://onlinelibrary.wiley.com/page/journal/10970118/homepage/editorialboard.html|access-date=27 May 2022}} and an editor for Combinatorica{{cite web|title=Combinatorica Editorial Board

|url=https://www.springer.com/journal/493/editors|access-date=27 May 2022}} and the Journal of Combinatorial Theory, Series B.{{cite web|title=Journal of Combinatorial Theory, Series B Editorial Board

|url=https://www.sciencedirect.com/journal/journal-of-combinatorial-theory-series-b/about/editorial-board|access-date=27 May 2022}}

File:PaulSeymour2010.jpg

Seymour's brother Leonard W. Seymour is Professor of gene therapy at Oxford University.{{Cite news|url=http://news.bbc.co.uk/1/hi/health/6251303.stm|title=Cold virus to aid cancer patients|date=11 January 2007}}

Combinatorics in Oxford in the 1970s was dominated by matroid theory, due to the influence of Dominic Welsh and Aubrey William Ingleton. Much of Seymour's early work, up to about 1980, was on matroid theory, and included three important matroid results: his D.Phil. thesis on matroids with the max-flow min-cut property{{cite journal |last1=Seymour |first1=P.D. |title=The matroids with the max-flow min-cut property |journal=Journal of Combinatorial Theory, Series B |date=1977 |volume=23 |issue=2–3 |pages=189–222 |doi=10.1016/0095-8956(77)90031-4|doi-access=free }} (for which he won his first Fulkerson prize); a characterisation by excluded minors of the matroids representable over the three-element field;{{cite journal |last1=Seymour, P.D. |title=The matroids representable over $\{\backslash rm\; GF\}(3)$ |journal=Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) |date=1978 |volume=260 |pages=381–383 |series=Colloq. Internat. CNRS}} and a theorem that all regular matroids consist of graphic and cographic matroids pieced together in a simple way{{cite journal |last1=Seymour |first1=P.D. |title=Decomposition of regular matroids |journal=Journal of Combinatorial Theory, Series B |date=1980 |volume=28 |issue=3 |pages=305–359 |doi=10.1016/0095-8956(80)90075-1|doi-access= }} (which won his first Pólya prize). There were several other significant papers from this period: a paper with Welsh on the critical probabilities for bond percolation on the square lattice;{{cite journal |last1=Seymour |first1=P.D. |author2-link=Dominic Welsh |last2=Welsh, D.J.A. |title=Percolation Probabilities on the Square Lattice |journal=Annals of Discrete Mathematics |date=1978 |volume=3 |pages=227–245 |doi=10.1016/S0167-5060(08)70509-0|isbn=9780720408430 }} a paper on edge-multicolouring of cubic graphs,{{cite journal |last1=Seymour |first1=P.D. |title=On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte |journal=Proceedings of the London Mathematical Society |date=1979 |volume=3 |issue=3 |pages=423–460 |doi=10.1112/plms/s3-38.3.423}} which foreshadows the matching lattice theorem of László Lovász; a paper proving that all bridgeless graphs admit nowhere-zero 6-flows,{{cite journal |last1=Seymour, P.D. |title=Nowhere-zero 6-flows| journal=Journal of Combinatorial Theory, Series B |date=1981| volume=30| issue=2|pages=130–135|doi=10.1016/0095-8956(81)90058-7|doi-access=free}} a step towards Tutte's nowhere-zero 5-flow conjecture; and a paper solving the two-paths problem (also introducing the cycle double cover conjecture),{{cite journal |last1=Seymour |first1=P.D. |title=Disjoint paths in graphs |journal=Discrete Mathematics |date=1980 |volume=29 |issue=3 |pages=293–309 |doi=10.1016/0012-365X(80)90158-2|doi-access= }} which was the engine behind much of Seymour's future work.

In 1980 he moved to Ohio State University, and began work with Neil Robertson. This led eventually to Seymour's most important accomplishment, the so-called "Graph Minors Project", a series of 23 papers (joint with Robertson), published over the next thirty years, with several significant results:

the graph minors structure theorem, that for any fixed graph, all graphs that do not contain it as a minor can be built from graphs that are essentially of bounded genus by piecing them together at small cutsets in a tree structure;{{cite journal |last1=Robertson, N. |last2=Seymour |first2=P. |title=Graph minors. XVII. Taming a vortex |journal=Journal of Combinatorial Theory, Series B |date=1999 |volume=77 |issue=1 |pages=162–210 |doi=10.1006/jctb.1999.1919|author1-link= Neil Robertson (mathematician)|doi-access=free }}

a proof of a conjecture of Wagner that in any infinite set of graphs, one of them is a minor of another (and consequently that any property of graphs that can be characterised by excluded minors can be characterised by a finite list of excluded minors);{{cite journal |last1=Robertson, N. |last2=Seymour |first2=P. |title=Graph minors. XX. Wagner's conjecture |journal=Journal of Combinatorial Theory, Series B |date=2004 |volume=92 |issue=2 |pages=325–357 |doi=10.1016/j.jctb.2004.08.001|author1-link= Neil Robertson (mathematician)|doi-access=free }}

a proof of a similar conjecture of Nash-Williams that in any infinite set of graphs, one of them can be immersed in another;{{cite journal |last1=Robertson, N. |last2=Seymour |first2=P. |title=Graph minors XXIII. Nash-Williams' immersion conjecture |journal=Journal of Combinatorial Theory, Series B |date=2010 |volume=100 |issue=2 |pages=181–205 |doi=10.1016/j.jctb.2009.07.003|author1-link= Neil Robertson (mathematician)|doi-access=free |citeseerx=10.1.1.304.8831 }}

and polynomial-time algorithms to test if a graph contains a fixed graph as a minor, and to solve the k vertex-disjoint paths problem for all fixed k.{{cite journal |last1=Robertson, N. |last2=Seymour |first2=P. |title=Graph minors. XIII. The disjoint paths problem |journal=Journal of Combinatorial Theory, Series B |date=1995 |volume=63 |issue=1 |pages=65–110 |doi=10.1006/jctb.1995.1006|author1-link= Neil Robertson (mathematician)|doi-access=free }}

In about 1990 Robin Thomas began to work with Robertson and Seymour. Their collaboration resulted in several important joint papers over the next ten years:

a proof of a conjecture of Sachs, characterising by excluded minors the graphs that admit linkless embeddings in 3-space;{{cite journal |last1=Robertson, N. |last2=Seymour, P. |last3=Thomas, R. |title=Sachs' linkless embedding conjecture |journal=Journal of Combinatorial Theory, Series B |date=1995 |volume=64 |issue=2 |pages=185–227 |doi=10.1006/jctb.1995.1032|author1-link=Neil Robertson (mathematician) |author2-link=Paul Seymour (mathematician) |author3-link=Robin Thomas (mathematician) |doi-access=free }}

a proof that every graph that is not five-colourable has a six-vertex complete graph as a minor (the four-colour theorem is assumed to obtain this result, which is a case of Hadwiger's conjecture);{{cite journal |last1=Robertson, N. |last2=Seymour, P. |last3=Thomas, R. |title=Hadwiger's conjecture for $K\_6$-free graphs |journal=Combinatorica |date=1993 |volume=13 |issue=3 |pages=279–361 |doi=10.1007/BF01202354|s2cid=9608738 |author1-link=Neil Robertson (mathematician) |author3-link=Robin Thomas (mathematician) }}

with Dan Sanders, a new, simplified, computer based proof of the four-colour theorem;{{cite journal |last1=Robertson, N. |last2=Sanders, D. |last3=Seymour, P. |last4=Thomas, R. |title=The four-colour theorem |journal=Journal of Combinatorial Theory, Series B |date=1997 |volume=70 |issue=1 |pages=2–44 |doi=10.1006/jctb.1997.1750|author1-link=Neil Robertson (mathematician) |author2-link=Daniel P. Sanders |author4-link=Robin Thomas (mathematician) |doi-access=free }}

and a description of the bipartite graphs that admit Pfaffian orientations.{{cite journal |last1=Robertson, N. |last2=Seymour, P. |last3=Thomas, R. |title=Permanents, Pfaffian orientations, and even directed circuits |journal=Annals of Mathematics |date=1999 |volume=150 |issue=3 |pages=929–975 |doi=10.2307/121059|jstor=121059 |arxiv=math/9911268 |s2cid=7489315 |author1-link=Neil Robertson (mathematician) |author3-link=Robin Thomas (mathematician) }}

In the same period, Seymour and Thomas also published several significant results: (with Noga Alon) a separator theorem for graphs with an excluded minor,{{cite journal |last1=Alon, N. |last2=Seymour, P. |last3=Thomas, R. |title=A separator theorem for nonplanar graphs |journal=Journal of the American Mathematical Society |date=1990 |volume=3 |issue=4 |pages=801–808 |doi=10.2307/1990903|jstor=1990903 |author1-link=Noga Alon |author3-link=Robin Thomas (mathematician) |doi-access=free }} extending the planar separator theorem of Richard Lipton and Robert Tarjan; a paper characterizing treewidth in terms of brambles;{{cite journal |last1=Seymour, P. |last2=Thomas, R. |title=Graph searching and a min-max theorem for tree-width |journal=Journal of Combinatorial Theory, Series B |date=1993 |volume=58 |issue=1 |pages=22–33 |doi=10.1006/jctb.1993.1027|author2-link=Robin Thomas (mathematician) |doi-access=free }} and a polynomial-time algorithm to compute the branch-width of planar graphs.{{cite journal |last1=Seymour, P. |last2=Thomas, R. |title=Call routing and the ratcatcher |journal=Combinatorica |date=1994 |volume=14 |issue=2 |pages=217–241 |doi=10.1007/BF01215352|s2cid=7508434 |author2-link=Robin Thomas (mathematician) }}

In 2000 Robertson, Seymour, and Thomas were supported by the American Institute of Mathematics to work on the strong perfect graph conjecture, a famous open question that had been raised by Claude Berge in the early 1960s. Seymour's student Maria Chudnovsky joined them in 2001, and in 2002 the four jointly proved the conjecture.{{cite journal |last1=Chudnovsky, M. |last2=Robertson, N. |last3=Seymour, P. |last4=Thomas, R. |title=The strong perfect graph theorem |journal=Annals of Mathematics |date=2006 |volume=164 |issue=1 |pages=51–229 |doi=10.4007/annals.2006.164.51|s2cid=119151552 |author1-link=Maria Chudnovsky |author2-link=Neil Robertson (mathematician) |author4-link=Robin Thomas (mathematician) |doi-access=free |arxiv=math/0212070 }} Seymour continued to work with Chudnovsky, and obtained several more results about induced subgraphs, in particular (with Cornuéjols, Liu, and Vušković) a polynomial-time algorithm to test whether a graph is perfect,{{cite journal |last1=Chudnovsky, M. |last2=Cornuéjols, G |last3=Liu, X. |last4=Seymour, P. |last5=Vus̆ković, K. |title=Recognizing Berge graphs |journal=Combinatorica |date=2005 |volume=25 |issue=2 |pages=143–186 |doi=10.1007/s00493-005-0012-8|s2cid=2229369 |author1-link=Maria Chudnovsky |author2-link=Gérard Cornuéjols |author5-link=Kristina_Vušković }} and a general description of all claw-free graphs.{{cite journal |last1=Chudnovsky, M. |last2=Seymour, P. |title=Claw-free graphs. V. Global structure |journal=Journal of Combinatorial Theory, Series B |date=2008 |volume=98 |issue=6 |pages=1373–1410 |doi=10.1016/j.jctb.2008.03.002|author1-link=Maria Chudnovsky |doi-access=free |citeseerx=10.1.1.125.1835 }} Other important results in this period include: (with Seymour's student Sang-il Oum) fixed-parameter tractable algorithms to approximate the clique-width of graphs (within an exponential bound) and the branch-width of matroids (within a linear bound);{{cite journal |last1=Oum, S. |last2=Seymour, P. |title=Approximating clique-width and branch-width |journal=Journal of Combinatorial Theory, Series B |date=2006 |volume=96 |issue=4 |pages=514–528 |doi=10.1016/j.jctb.2005.10.006|author1-link=Oum Sang-il |doi-access=free |citeseerx=10.1.1.139.9829 }} and (with Chudnovsky) a proof that the roots of the independence polynomial of every claw-free graph are real.{{cite journal |last1=Chudnovsky, M. |last2=Seymour, P. |title=The roots of the independence polynomial of a clawfree graph |journal=Journal of Combinatorial Theory, Series B |date=2007 |volume=97 |issue=3 |pages=350–357 |doi=10.1016/j.jctb.2006.06.001|author1-link=Maria Chudnovsky |doi-access=free |citeseerx=10.1.1.118.3609 }}

In the 2010s Seymour worked mainly on χ-boundedness and the Erdős–Hajnal conjecture. In a series of papers with Alex Scott and partly with Chudnovsky, they proved two conjectures of András Gyárfás, that every graph with bounded clique number and sufficiently large chromatic number has an induced cycle of odd length at least five,{{cite journal |last1=Scott, A. |last2=Seymour, P. |title=Induced subgraphs of graphs with large chromatic number. I. Odd holes |journal=Journal of Combinatorial Theory, Series B |date=2016 |volume=121 |pages=68–86 |doi=10.1016/j.jctb.2015.10.002|s2cid=52874586 |doi-access=free |arxiv=1410.4118 }} and has an induced cycle of length at least any specified number.{{cite journal |last1=Chudnovsky, M. |last2=Scott, A. |last3=Seymour, P. |title=Induced subgraphs of graphs with large chromatic number. III. Long holes |journal=Combinatorica |date=2017 |volume=37 |issue=6 |pages=1057–1072 |doi=10.1007/s00493-016-3467-x|arxiv=1506.02232 |s2cid=2560430 |author1-link=Maria Chudnovsky }} The series culminated in a paper of Scott and Seymour proving that for every fixed k, every graph with sufficiently large chromatic number contains either a large complete subgraph or induced cycles of all lengths modulo k,{{cite journal |last1=Scott, A. |last2=Seymour, P. |title=Induced subgraphs of graphs with large chromatic number. X. Holes with specific residue |journal=Combinatorica |date=2019 |volume=39 |issue=5 |pages=1105–1132 |doi=10.1007/s00493-019-3804-y|arxiv=1705.04609 |s2cid=51746725 }} which leads to the resolutions of two conjectures of Gil Kalai and Roy Meshulam connecting the chromatic number of a graph with the homology of its independence complex. There was also a polynomial-time algorithm (with Chudnovsky, Scott, and Chudnovsky and Seymour's student Sophie Spirkl) to test whether a graph contains an induced cycle with length more than three and odd.{{cite journal |last1=Chudnovsky, M. |last2=Scott, A. |last3=Seymour, P. |last4=Spirkl, S. |title=Detecting an odd hole |journal=Journal of the ACM |date=2020 |volume=67 |issue=1 |page=12pp |doi=10.1145/3375720|s2cid=119705201 |author1-link=Maria Chudnovsky |doi-access=free |hdl=10012/18527 |hdl-access=free }} Most recently, the four jointly resolved the 5-cycle case of the Erdős–Hajnal conjecture, which says that every graph without an induced copy of the 5-cycle contains an independent set or a clique of polynomial size.{{cite journal |last1=Chudnovsky, M. |last2=Scott, A. |last3=Seymour, P. |last4=Spirkl, S. |title=Erdős–Hajnal for graphs with no 5-hole |journal=Proceedings of the London Mathematical Society |date=2023 |volume=126 |issue=3 |pages=997–1014 |doi=10.1112/plms.12504| arxiv=2102.04994|s2cid=259380697|author1-link=Maria Chudnovsky }}

{{Reflist|group=pub}}

• Robertson–Seymour theorem
• Strong perfect graph theorem

{{Reflist}}

{{Commons}}

• [http://www.math.princeton.edu/~pds/ Paul Seymour home page] at Princeton University
• {{MathGenealogy|id=50728|title=Paul Seymour}}

{{Authority control}}

{{DEFAULTSORT:Seymour, Paul}}

Category:Year of birth missing (living people)

Category:Living people

Category:20th-century American mathematicians

Category:21st-century American mathematicians

Category:Graph theorists

Category:Alumni of Exeter College, Oxford

Category:Ohio State University faculty

Category:Princeton University faculty

Category:People educated at Plymouth College

Category:Fellows of Merton College, Oxford

Category:Fellows of the Royal Society