Seymour, Paul (mathematician)

He studied at Plymouth College, then at Exeter College in Oxford, receiving a bachelor 's degree in 1971 and a Ph.D. in 1975.

Between 1974 and 1976, he was a college research fellow at Swansea University College . Then he returned to Oxford, where he worked in 1976-1980 as a junior research fellow at Merton College, and in 1978-1979 he worked at the University of Waterloo . In 1980-1983, he was an associate professor and then professor at the Ohio State Research University in Columbus , where he began research with Neil Robertson, a fruitful collaboration that continued for many years. From 1983 to 1996, he worked at Bellcore (Bell Communications Research, now Telcordia Technologies) in Morristown . He was also an associate professor at Rutgers University in 1984-1987 and at Waterloo University in 1988-1993. In 1996 he became a professor at Princeton University .

Paul Seymour in 2007
(photo from MFIs)

In 1979, he married Shelley MacDonald from Ottawa , married with two children - Amy and Emily. The couple broke up in 2007. Brother - Linord Seymour - Professor of Gene Therapy at Oxford University .

Combinatorics at Oxford in the 1970s dominated the theory of matroids, thanks to the influence of Dominic Welch and Aubrey William Ingleton. Most of Seymour's early works, until about 1980, were devoted to the theory of matroids and included three important works on matroids: a doctoral dissertation; work on the characterization of excluded minors of matroids represented above a three-element field; and the theorem that all regular matroids consist of graph and cograph matroids assembled together in a simple way (the result for which the Polya prize was awarded). Since this period, there have been several other significant works: an article with Welch on the critical probabilities of seeping communications on a square lattice; an article that discloses the double-loop hypothesis; an article on the boundary multicolorness of cubic graphs, which portends the coincidence lattice theorem of Laszlo Lovas; an article proving that all bridgeless graphs admit nowhere non-zero 6-flows is a step towards confirming the Tatt hypothesis about nowhere non-zero 5 -flows, and an article solving the two-way problem that was the engine of most of Seymour's future work.

In 1980, he moved to Ohio State University, where he began working with Neil Robertson, collaborating on the so-called “draft graph minors” - a series of 23 articles published over the next thirty years, with several significant results: graph structure theorem for minors, that for any fixed graph, all graphs that do not contain it as a minor can be constructed from graphs that are essentially of a limited genus, combining them together on small sets of cutouts in a tree structure; proof of Wagner's hypothesis that in any infinite set of graphs one of them is a minor of the other (and, therefore, any property of graphs that can be characterized by excluded minors can be characterized by a finite list of excluded minors); proof of a similar Nash-Williams hypothesis that in any infinite set of graphs one of them can be immersed in the other; polynomial time algorithms to check whether a graph contains a fixed graph as a minor, and solve the problem of vertex-disjoint paths for all fixed k.

Around 1990, Robin Thomas began working with Robertson and Seymour. As a result of their cooperation over the next ten years, several important joint articles were prepared: the proof of the Sachs hypothesis, characterizing excluded minors graphs that allow incoherent investments in 3-space; proof that every graph that is not five-color has a complete graph with six vertices as a minor graph (it is assumed that the four-color theorem gives this result, which is a case of the Hadwiger hypothesis ); with Dan Sanders a new, simplified, computer proof of the four-color theorem; description of bipartite graphs that admit Pfaffian orientation; and the reduction to an almost flat case of Tatt's conjecture that every cubic graph without a bridge that is not triplicate contains the Petersen graph as a minor. (The remaining “almost flat case” was subsequently resolved, thereby obtaining a complete proof of the Tatt hypothesis; the solution does not use the four-color theorem, and, moreover, proves it in an expanded form).

In 2000, the trio was supported by the American Institute of Mathematics to work on the strong hypothesis of an ideal graph, an open problem raised by Claude Berge in the early 1960s. Student Seymour Maria Chudnovskaya joined the group in 2001, and in 2002 the four together proved the hypothesis. Seymour continued to work with Chudnovskaya and obtained several more results on induced subgraphs, in particular (with three co-authors) the polynomial time algorithm for checking whether a graph is perfect and a general description of all graphs without claws . The Robertson – Seymour theorem is a result obtained in 2004 on the basis of the work of the “project of graph minors,” which establishes a completely quasi-ordering of a multitude of undirected graphs with a minority relation.

In the 2010s, in a series of works with Alex Scott and partly with Chudnovskaya, two hypotheses of Andras Dyarfash were proved that each graph with a limited number of cliques and a sufficiently large chromatic number has an odd-length induced cycle of at least five and has an induced cycle of at least any length the specified number.

• Paul Seymour Homepage at Princeton University