Paul Seymour (mathematician)

Last updated

Paul Seymour

FRS
PaulSeymour2010.jpg
Born (1950-07-26) 26 July 1950 (age 73)
Plymouth, Devon, England
NationalityBritish
Alma mater University of Oxford (BA, PhD)
Awards Sloan Fellowship (1983)
Ostrowski Prize (2003)
George Pólya Prize (1983, 2004)
Fulkerson Prize (1979, 1994, 2006, 2009)
Scientific career
Institutions Princeton University
Bellcore
University of Waterloo
Rutgers University
Ohio State University
Doctoral advisor Aubrey William Ingleton
Doctoral students Maria Chudnovsky
Sang-il Oum

Paul D. Seymour FRS (born 26 July 1950) is a British mathematician known for his work in discrete mathematics, especially graph theory. He (with others) was responsible for important 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, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website. [1]

Contents

Seymour is currently the Albert Baldwin Dod Professor of Mathematics at Princeton University. [2] He won a Sloan Fellowship in 1983, and the Ostrowski Prize in 2003; [3] 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, one from the Technical University of Denmark in 2013, and one from the École normale supérieure de Lyon in 2022. He was an invited speaker in the 1986 International Congress of Mathematicians and a plenary speaker in the 1994 International Congress of Mathematicians. He became a Fellow of the Royal Society in 2022. [4]

Early life

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.

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, with the year 1978–79 at University of Waterloo. [5] 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. [5] He is Editor-in-Chief (jointly with Carsten Thomassen) for the Journal of Graph Theory , [6] and an editor for Combinatorica [7] and the Journal of Combinatorial Theory, Series B . [8]

Paul Seymour in 2007 (photo from MFO) Paul Seymour.jpeg
Paul Seymour in 2007
(photo from MFO)

Personal life

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

Major contributions

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 [pub 1] (for which he won his first Fulkerson prize); a characterisation by excluded minors of the matroids representable over the three-element field; [pub 2] and a theorem that all regular matroids consist of graphic and cographic matroids pieced together in a simple way [pub 3] (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; [pub 4] a paper on edge-multicolouring of cubic graphs, [pub 5] which foreshadows the matching lattice theorem of László Lovász; a paper proving that all bridgeless graphs admit nowhere-zero 6-flows, [pub 6] 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), [pub 7] 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; [pub 8] 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); [pub 9] a proof of a similar conjecture of Nash-Williams that in any infinite set of graphs, one of them can be immersed in another; [pub 10] 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. [pub 11]

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; [pub 12] 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); [pub 13] with Dan Sanders, a new, simplified, computer based proof of the four-colour theorem; [pub 14] and a description of the bipartite graphs that admit Pfaffian orientations. [pub 15] In the same period, Seymour and Thomas also published several significant results: (with Noga Alon) a separator theorem for graphs with an excluded minor, [pub 16] extending the planar separator theorem of Richard Lipton and Robert Tarjan; a paper characterizing treewidth in terms of brambles; [pub 17] and a polynomial-time algorithm to compute the branch-width of planar graphs. [pub 18]

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. [pub 19] 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, [pub 20] and a general description of all claw-free graphs. [pub 21] 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); [pub 22] and (with Chudnovsky) a proof that the roots of the independence polynomial of every claw-free graph are real. [pub 23]

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, [pub 24] and has an induced cycle of length at least any specified number. [pub 25] 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, [pub 26] 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. [pub 27] 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. [pub 28]

Selected publications

  1. ↑ Seymour, P.D. (1977). "The matroids with the max-flow min-cut property". Journal of Combinatorial Theory, Series B . 23 (2–3): 189–222. doi: 10.1016/0095-8956(77)90031-4 .
  2. ↑ Seymour, P.D. (1978). "The matroids representable over ". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloq. Internat. CNRS. 260: 381–383.
  3. ↑ Seymour, P.D. (1980). "Decomposition of regular matroids". Journal of Combinatorial Theory, Series B . 28 (3): 305–359. doi:10.1016/0095-8956(80)90075-1.
  4. ↑ Seymour, P.D.; Welsh, D.J.A. (1978). "Percolation Probabilities on the Square Lattice". Annals of Discrete Mathematics. 3: 227–245. doi:10.1016/S0167-5060(08)70509-0. ISBN   9780720408430.
  5. ↑ Seymour, P.D. (1979). "On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte". Proceedings of the London Mathematical Society . 3 (3): 423–460. doi:10.1112/plms/s3-38.3.423.
  6. ↑ Seymour, P.D. (1981). "Nowhere-zero 6-flows". Journal of Combinatorial Theory, Series B . 30 (2): 130–135. doi: 10.1016/0095-8956(81)90058-7 .
  7. ↑ Seymour, P.D. (1980). "Disjoint paths in graphs". Discrete Mathematics . 29 (3): 293–309. doi:10.1016/0012-365X(80)90158-2.
  8. ↑ Robertson, N.; Seymour, P. (1999). "Graph minors. XVII. Taming a vortex". Journal of Combinatorial Theory, Series B . 77 (1): 162–210. doi: 10.1006/jctb.1999.1919 .
  9. ↑ Robertson, N.; Seymour, P. (2004). "Graph minors. XX. Wagner's conjecture". Journal of Combinatorial Theory, Series B . 92 (2): 325–357. doi: 10.1016/j.jctb.2004.08.001 .
  10. ↑ Robertson, N.; Seymour, P. (2010). "Graph minors XXIII. Nash-Williams' immersion conjecture". Journal of Combinatorial Theory, Series B . 100 (2): 181–205. CiteSeerX   10.1.1.304.8831 . doi: 10.1016/j.jctb.2009.07.003 .
  11. ↑ Robertson, N.; Seymour, P. (1995). "Graph minors. XIII. The disjoint paths problem". Journal of Combinatorial Theory, Series B . 63 (1): 65–110. doi: 10.1006/jctb.1995.1006 .
  12. ↑ Robertson, N.; Seymour, P.; Thomas, R. (1995). "Sachs' linkless embedding conjecture". Journal of Combinatorial Theory, Series B . 64 (2): 185–227. doi: 10.1006/jctb.1995.1032 .
  13. ↑ Robertson, N.; Seymour, P.; Thomas, R. (1993). "Hadwiger's conjecture for -free graphs". Combinatorica . 13 (3): 279–361. doi:10.1007/BF01202354. S2CID   9608738.
  14. ↑ Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. (1997). "The four-colour theorem". Journal of Combinatorial Theory, Series B . 70 (1): 2–44. doi: 10.1006/jctb.1997.1750 .
  15. ↑ Robertson, N.; Seymour, P.; Thomas, R. (1999). "Permanents, Pfaffian orientations, and even directed circuits". Annals of Mathematics . 150 (3): 929–975. arXiv: math/9911268 . doi:10.2307/121059. JSTOR   121059. S2CID   7489315.
  16. ↑ Alon, N.; Seymour, P.; Thomas, R. (1990). "A separator theorem for nonplanar graphs". Journal of the American Mathematical Society . 3 (4): 801–808. doi: 10.2307/1990903 . JSTOR   1990903.
  17. ↑ Seymour, P.; Thomas, R. (1993). "Graph searching and a min-max theorem for tree-width". Journal of Combinatorial Theory, Series B . 58 (1): 22–33. doi: 10.1006/jctb.1993.1027 .
  18. ↑ Seymour, P.; Thomas, R. (1994). "Call routing and the ratcatcher". Combinatorica . 14 (2): 217–241. doi:10.1007/BF01215352. S2CID   7508434.
  19. ↑ Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R. (2006). "The strong perfect graph theorem". Annals of Mathematics . 164 (1): 51–229. arXiv: math/0212070 . doi: 10.4007/annals.2006.164.51 . S2CID   119151552.
  20. ↑ Chudnovsky, M.; Cornuéjols, G; Liu, X.; Seymour, P.; Vus̆ković, K. (2005). "Recognizing Berge graphs". Combinatorica . 25 (2): 143–186. doi:10.1007/s00493-005-0012-8. S2CID   2229369.
  21. ↑ Chudnovsky, M.; Seymour, P. (2008). "Claw-free graphs. V. Global structure". Journal of Combinatorial Theory, Series B . 98 (6): 1373–1410. CiteSeerX   10.1.1.125.1835 . doi: 10.1016/j.jctb.2008.03.002 .
  22. ↑ Oum, S.; Seymour, P. (2006). "Approximating clique-width and branch-width". Journal of Combinatorial Theory, Series B . 96 (4): 514–528. CiteSeerX   10.1.1.139.9829 . doi: 10.1016/j.jctb.2005.10.006 .
  23. ↑ Chudnovsky, M.; Seymour, P. (2007). "The roots of the independence polynomial of a clawfree graph". Journal of Combinatorial Theory, Series B . 97 (3): 350–357. CiteSeerX   10.1.1.118.3609 . doi: 10.1016/j.jctb.2006.06.001 .
  24. ↑ Scott, A.; Seymour, P. (2016). "Induced subgraphs of graphs with large chromatic number. I. Odd holes". Journal of Combinatorial Theory, Series B . 121: 68–86. arXiv: 1410.4118 . doi: 10.1016/j.jctb.2015.10.002 . S2CID   52874586.
  25. ↑ Chudnovsky, M.; Scott, A.; Seymour, P. (2017). "Induced subgraphs of graphs with large chromatic number. III. Long holes". Combinatorica . 37 (6): 1057–1072. arXiv: 1506.02232 . doi:10.1007/s00493-016-3467-x. S2CID   2560430.
  26. ↑ Scott, A.; Seymour, P. (2019). "Induced subgraphs of graphs with large chromatic number. X. Holes with specific residue". Combinatorica . 39 (5): 1105–1132. arXiv: 1705.04609 . doi:10.1007/s00493-019-3804-y. S2CID   51746725.
  27. ↑ Chudnovsky, M.; Scott, A.; Seymour, P.; Spirkl, S. (2020). "Detecting an odd hole". Journal of the ACM . 67 (1): 12pp. doi: 10.1145/3375720 . hdl: 10012/18527 . S2CID   119705201.
  28. ↑ Chudnovsky, M.; Scott, A.; Seymour, P.; Spirkl, S. (2023). "Erdős–Hajnal for graphs with no 5-hole". Proceedings of the London Mathematical Society . 126 (3): 997–1014. arXiv: 2102.04994 . doi:10.1112/plms.12504. S2CID   259380697.

See also

Related Research Articles

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Perfect graph theorem</span> An undirected graph is perfect if and only if its complement graph is also perfect

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

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 each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Hadwiger number</span> Size of largest complete graph made by contracting edges of a given graph

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

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 applications of combinatorics. Series B is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as JCTA and JCTB.

<span class="mw-page-title-main">Branch-decomposition</span> Hierarchical clustering of graph edges

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

<span class="mw-page-title-main">Klaus Wagner</span>

Klaus Wagner was a German mathematician known for his contributions to graph theory.

In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices. More precisely, the definition may allow the graph to have induced cycles of length four, or may also disallow them: the latter is referred to as even-cycle-free graphs.

<span class="mw-page-title-main">Maria Chudnovsky</span> Mathematician and engineer

Maria Chudnovsky is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow.

<span class="mw-page-title-main">Bull graph</span>

In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges.

<span class="mw-page-title-main">Skew partition</span>

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In the mathematical theory of matroids, a minor of a matroid M is another matroid N that is obtained from M by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs.

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, who first posed it as an open problem in a paper from 1977.

In graph theory, a -bounded family of graphs is one for which there is some function such that, for every integer the graphs in with can be colored with at most colors. The function is called a -binding function for . These concepts and their notations were formulated by András Gyárfás. The use of the Greek letter chi in the term -bounded is based on the fact that the chromatic number of a graph is commonly denoted . An overview of the area can be found in a survey of Alex Scott and Paul Seymour.

In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree and complete graph , the graphs with neither nor as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whether the -free graphs are -bounded. It is named after András Gyárfás and David Sumner, who formulated it independently in 1975 and 1981 respectively. It remains unproven.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.