Paul D. Seymour (born 26 July 1950) is a British

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

known for his work in

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, especially

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

. He (with others) was responsible for important progress on

regular matroid In mathematics, a regular matroid is a matroid that can be represented over all fields. Definition A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". On ...

s and totally unimodular matrices, the

four colour theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...

linkless embedding In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is ...

s, graph minors and structure, the

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

conjecture, the

Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...

s, χ-boundedness, and the

Erdős–Hajnal conjecture In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal. ...

. Many of his recent papers are available from his website. Seymour is currently the

Albert Baldwin Dod Albert Baldwin Dod (March 24, 1805 – November 20, 1845) was an American Presbyterian theologian and professor of mathematics. Early life Dod was born on March 24, 1805 in Mendham, New Jersey. He was the son of Daniel Dod (1778–1823) and Nanc ...

Professor of

Mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

. He won a

Sloan Fellowship The Sloan Research Fellowships are awarded annually by the Alfred P. Sloan Foundation since 1955 to "provide support and recognition to early-career scientists and scholars". This program is one of the oldest of its kind in the United States. ...

in 1983, and the

Ostrowski Prize The Ostrowski Prize is a mathematics award given every odd year for outstanding mathematical achievement judged by an international jury from the universities of Basel, Jerusalem, Waterloo and the academies of Denmark and the Netherlands. Alexan ...

in 2004; and (sometimes with others) won the

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

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 The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...

in 2008, one from the

Technical University of Denmark The Technical University of Denmark ( da, Danmarks Tekniske Universitet), often simply referred to as DTU, is a polytechnic university and school of engineering. It was founded in 1829 at the initiative of Hans Christian Ørsted as Denmark's fi ...

in 2013, and one from the

École normale supérieure de Lyon The École normale supérieure de Lyon (also known as ENS de Lyon, ENSL or Normale Sup' Lyon) is a French grande école located in the city of Lyon. It is one of the four prestigious écoles normales supérieures in France. The school is ...

in 2022. He was an invited speaker in the 1986

International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the Nevanlinna Prize (to be rename ...

and a plenary speaker in the 1994

. He became a Fellow of the

Royal Society The Royal Society, formally The Royal Society of London for Improving Natural Knowledge, is a learned society and the United Kingdom's national academy of sciences. The society fulfils a number of roles: promoting science and its benefits, re ...

in 2022.

Early life

Seymour was born in

Plymouth Plymouth () is a port city and unitary authority in South West England. It is located on the south coast of Devon, approximately south-west of Exeter and south-west of London. It is bordered by Cornwall to the west and south-west. Plymouth ...

, Devon, England. He was a day student at

Plymouth College Plymouth College is a co-educational independent school in Plymouth, Devon. History The school was established in 1877. In 1896 Plymouth College bought Mannamead School (founded in 1854), and was temporarily known as Plymouth and Mannamead ...

, and then studied at

Exeter College, Oxford Exeter College (in full: The Rector and Scholars of Exeter College in the University of Oxford) is one of the Colleges of the University of Oxford, constituent colleges of the University of Oxford in England and the fourth-oldest college of the un ...

, gaining a BA degree in 1971, and

D.Phil A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

in 1975.

Career

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 Merton College (in full: The House or College of Scholars of Merton in the University of Oxford) is one of the Colleges of Oxford University, constituent colleges of the University of Oxford in England. Its foundation can be traced back to the ...

, with the year 1978–79 at

. He became an associate and then a full professor at

Ohio State University The Ohio State University, commonly called Ohio State or OSU, is a public land-grant research university in Columbus, Ohio. A member of the University System of Ohio, it has been ranked by major institutional rankings among the best publ ...

Columbus, Ohio Columbus () is the state capital and the most populous city in the U.S. state of Ohio. With a 2020 census population of 905,748, it is the 14th-most populous city in the U.S., the second-most populous city in the Midwest, after Chicago, and t ...

, between 1980 and 1983, where he began research with

Neil Robertson Neil Robertson (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...

, a fruitful collaboration that continued for many years. From 1983 until 1996, he was at

Bellcore iconectiv is a supplier of network planning and network management services to telecommunications providers. Known as Bellcore after its establishment in the United States in 1983 as part of the break-up of the Bell System, the company's name ...

(Bell Communications Research),

Morristown, New Jersey Morristown () is a town and the county seat of Morris County, in the U.S. state of New Jersey. ...

(now

Telcordia Technologies iconectiv is a supplier of network planning and network management services to telecommunications providers. Known as Bellcore after its establishment in the United States in 1983 as part of the break-up of the Bell System, the company's name ...

). He was also an adjunct professor at

Rutgers University Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's ...

from 1984 to 1987 and at the University of Waterloo from 1988 to 1993. He became professor at

in 1996. He is Editor-in-Chief (jointly with

Carsten Thomassen Carsten Thomassen may refer to: * Carsten Thomassen (mathematician) * Carsten Thomassen (journalist) Carsten Thomassen (15 May 1969 – 14 January 2008) was a Norway, Norwegian journalist, political commentator and war correspondent for the Norw ...

) for the ''

Journal of Graph Theory The ''Journal of Graph Theory'' is a peer-reviewed mathematics journal specializing in graph theory and related areas, such as structural results about graphs, graph algorithms with theoretical emphasis, and discrete optimization on graphs. The s ...

'', and an editor for ''

Combinatorica ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorar ...

'' and the ''

Journal of Combinatorial Theory, Series B The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

''.

Personal life

He married Shelley MacDonald of

Ottawa Ottawa (, ; Canadian French: ) is the capital city of Canada. It is located at the confluence of the Ottawa River and the Rideau River in the southern portion of the province of Ontario. Ottawa borders Gatineau, Quebec, and forms the core ...

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 Gene therapy is a medical field which focuses on the genetic modification of cells to produce a therapeutic effect or the treatment of disease by repairing or reconstructing defective genetic material. The first attempt at modifying human DN ...

Oxford University Oxford () is a city in England. It is the county town and only city of Oxfordshire. In 2020, its population was estimated at 151,584. It is north-west of London, south-east of Birmingham and north-east of Bristol. The city is home to the ...

Major contributions

Combinatorics in Oxford in the 1970s was dominated by

matroid theory In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in ...

, due to the influence of

Dominic Welsh James Anthony Dominic Welsh (known professionally as D.J.A. Welsh) (born 29 August 1938)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

s 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 on edge-multicolouring of cubic graphs, which foreshadows the matching lattice theorem of

László Lovász László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...

; 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 (also introducing the cycle double cover conjecture), 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 Wilhelm Richard Wagner ( ; ; 22 May 181313 February 1883) was a German composer, theatre director, polemicist, and conductor who is chiefly known for his operas (or, as some of his mature works were later known, "music dramas"). Unlike most op ...

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 Robin may refer to: Animals * Australasian robins, red-breasted songbirds of the family Petroicidae * Many members of the subfamily Saxicolinae (Old World chats), including: **European robin (''Erithacus rubecula'') ** Bush-robin **Forest ro ...

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 Sachs is a German surname, meaning "man from Saxony". Sachs is a common surname among Ashkenazi Jews from Saxony, in the United States sometimes adopted in the variant Zaks, supposedly in reference to the Hebrew phrase ''Zera Kodesh Shemo'' (ZaKS), ...

, characterising by excluded minors the graphs that admit

s 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; and a description of the bipartite graphs that admit Pfaffian orientations. In the same period, Seymour and Thomas also published several significant results: (with

Noga Alon Noga Alon ( he, נוגה אלון; born 17 February 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of ...

) a separator theorem for graphs with an excluded minor, extending the

planar separator theorem In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of verti ...

Richard Lipton Richard Jay Lipton (born September 6, 1946) is an American computer scientist who is Associate Dean of Research, Professor, and the Frederick G. Storey Chair in Computing in the College of Computing at the Georgia Institute of Technology. He has ...

and

Robert Tarjan Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees a ...

; a paper characterizing

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

in terms of

brambles A bramble is any rough, tangled, prickly shrub, usually in the genus ''Rubus'', which grows blackberries, raspberries, or dewberries. "Bramble" is also used to describe other prickly shrubs, such as roses (''Rosa'' species). The fruits inclu ...

; and a polynomial-time algorithm to compute the branch-width of planar graphs. In 2000 Robertson, Seymour, and Thomas were supported by the

American Institute of Mathematics The American Institute of Mathematics (AIM) is one of eight mathematical institutes in the United States, funded by the National Science Foundation (NSF). It was founded in 1994 by John Fry, co-founder of Fry's Electronics, and originally located ...

to work on the strong perfect graph conjecture, a famous open question that had been raised by

Claude Berge Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. Biography and professional history Claude Berge's parents were André Berge and Genevièv ...

in the early 1960s. Seymour's student

Maria Chudnovsky Maria Chudnovsky (born January 6, 1977) is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow. Education and career Chudnovsky is a professor in the department of mathematic ...

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, and Vušković) a polynomial-time algorithm to test whether a graph is perfect, and a general description of all claw-free graphs. Other important results in this period include: (with Seymour's student Sang-il Oum)

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

algorithms to approximate the

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum num ...

of graphs (within an exponential bound) and the branch-width of matroids (within a linear bound); and (with Chudnovsky) a proof that the roots of the independence polynomial of every claw-free graph are real. In the 2010s Seymour worked mainly on χ-boundedness and the

. In a series of papers with Alex Scott and partly with Chudnovsky, they proved two conjectures of

András Gyárfás András Gyárfás (born 1945) is a Hungarian mathematician who specializes in the study of graph theory. He is famous for two conjectures: * Together with Paul Erdős he conjectured what is now called the Erdős–Gyárfás conjecture which sta ...

, 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. 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, which leads to the resolutions of two conjectures of

Gil Kalai Gil Kalai (born 1955) is the Henry and Manya Noskwith Professor Emeritus of Mathematics at the Hebrew University of Jerusalem, Israel, Professor of Computer Science at the Interdisciplinary Center, Herzliya, and adjunct Professor of mathematics ...

and Roy Meshulam connecting the chromatic number of a graph with the

homology Homology may refer to: Sciences Biology *Homology (biology), any characteristic of biological organisms that is derived from a common ancestor * Sequence homology, biological homology between DNA, RNA, or protein sequences *Homologous chrom ...

of its

independence complex The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph ''G'', denoted by I(''G''), is an abstract simplicial complex (that is, a family of ...

. 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. 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.

Selected publications

References

External links

Paul Seymour home page
at Princeton University * {{DEFAULTSORT:Seymour, Paul 1950 births Living people 20th-century American mathematicians 21st-century American mathematicians Graph theorists Alumni of Exeter College, Oxford Ohio State University faculty Princeton University faculty People educated at Plymouth College Fellows of Merton College, Oxford Fellows of the Royal Society