Paul Seymour

Paul Seymour (born 26 July 1950) is currently a professor at Princeton University; half in the department of mathematics and half in the program in applied and computational math. His research interest is in discrete mathematics, especially graph theory. He (with others) was responsible for progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, and claw-free graphs. Many of his recent papers are available from his website.

He won a Sloan Fellowship in 1983, and the Ostrowski Prize in 2004; and (sometimes with others) won the Fulkerson Prize in 1979, 1994, 2006 and 2009, and the Pólya Prize in 1983 and 2004. He received an honorary doctorate from the University of Waterloo in 2008 and one from the Technical University of Denmark in 2013.

Seymour was born in Plymouth, Devon, England. He was a day student at Plymouth College, and then studied at Exeter College, Oxford, gaining a BA degree in 1971, and D.Phil in 1975.

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. 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. He is Editor-in-Chief (jointly with Carsten Thomassen) for the Journal of Graph Theory.

He married Shelley MacDonald of Ottawa in 1979, and they have two children, Amy and Emily. The couple separated amicably in 2007. His brother Leonard W. Seymour is Professor of gene therapy at Oxford University.

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 (for which he won his first Fulkerson prize); a characterisation by excluded minors of the matroids representable over the three-element field; and a theorem that all regular matroids consist of graphic and cographic matroids pieced together in a simple way (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; a paper in which the cycle double cover conjecture was introduced; a paper on edge-multicolouring of cubic graphs, which foreshadows the matching lattice theorem of László Lovász; a paper proving that all bridgeless graphs admit nowhere-zero 6-flows, a step towards Tutte's nowhere-zero 5-flow conjecture; and a paper solving the two-paths problem, 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; 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); a proof of a similar conjecture of Nash-Williams that in any infinite set of graphs, one of them can be immersed in another; 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.

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; 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); with Dan Sanders, a new, simplified, computer based proof of the four-colour theorem; a description of the bipartite graphs that admit Pfaffian orientations; and the reduction to the ``almost-planar case of a conjecture of Tutte that every bridgeless cubic graph that is not three-edge-colourable contains the Petersen graph as a minor. (The remaining ``almost-planar case has now been solved, completing the proof of Tutte's conjecture, in papers by subsets of Sanders, Seymour, Thomas and Katherine Edwards. This does not assume the four-colour theorem, and re-proves it in an extended form).

In 2000 the trio 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. Seymour continued to work with Chudnovsky, and obtained several more results about induced subgraphs, in particular (with Cornuéjols, Liu, Vuskovic) a polynomial-time algorithm to test whether a graph is perfect, and a general description of all claw-free graphs. Most recently, 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, and has an induced cycle of length at least any specified number.