1.1. The Fulkerson Prize.

The Fulkerson Prize is awarded for outstanding papers in the area of discrete mathematics. The term "discrete mathematics" is interpreted broadly and is intended to include graph theory, networks, mathematical programming, applied combinatorics, applications of discrete mathematics to computer science, and related subjects. Originally, the prizes were paid out of a memorial fund administered by the American Mathematical Society that was established by friends of the late Delbert Ray Fulkerson (1924-1976) to encourage mathematical excellence in the fields of research exemplified by his work. Up to three awards of US$1500 each are presented at each (triennial) International Symposium of the Mathematical Programming Society.

The prize is presented for papers published during the six calendar years preceding the year in which the prize is given. The prize is given for single papers, not series of papers or books, and in the event of joint authorship, the prize is divided.

1.2. The 1979 Fulkerson Prize.

The Selection Committee for the 1979 Fulkerson Prize was R Graham, V Klee and A Tucker.

One of the three 1979 D R Fulkerson Prizes was awarded to Paul D Seymour for his paper 'The matroids with the max-flow min-cut property', Journal of Combinatorial Theory, Series B 23 (1977), 189-222.

1.3. Abstract of the winning paper.

The max-flow min-cut theorem of Ford and Fulkerson (for undirected networks) may be regarded as a statement about the circuits and cocircuits using some fixed element of the cycle matroid of a graph. We show that, in general, a matroid has this property (in the integer form) if and only if it is binary and has no minor isomorphic to the dual of the Fano matroid.

1.4. From András Frank's review of the paper.

This paper yields a through insight into min-max theorems of graph theory and their relations. It belongs to a series of articles by the author concerning such concepts as clutter minor, matroid ports, characterisation by forbidden minors etc.

2.1. The G Polya Prize.

The George Pólya Prize in Applied Combinatorics is awarded by the Society for Industrial and Applied Mathematics. The George Pólya Prize was established in 1969 as a quadrennial prize in combinatorics. The prize is broadly intended to recognise specific work. It was first awarded in 1971.

2.2 The 1983 G Polya Prize.

The 1983 G Polya Prize was awarded to Anders Bjorner and Paul Seymour.

3.1. The 1994 Fulkerson Prize.

The Selection Committee for the 1994 Prize was A Schrijver, A Hoffman and É Tardos.

One of the three 1994 D R Fulkerson Prizes was awarded to Neil Robertson, Paul D Seymour and Robin Thomas for their joint paper 'Hadwiger's conjecture for $K_{6}$-free graphs', Combinatorica 13 (1993) 279-361.

3.2. Abstract of the winning paper.

In 1943, Hadwiger made the conjecture that every loopless graph not contractible to the complete graph on $t + 1$ vertices is $t$-colourable. When $t ≤ 3$ this is easy, and when $t = 4$, Wagner's theorem of 1937 shows the conjecture to be equivalent to the four-colour conjecture (the 4CC). However, when $t ≥ 5$ it has remained open. Here we show that when $t = 5$ it is also equivalent to the 4CC. More precisely, we show (without assuming the 4CC) that every minimal counterexample to Hadwiger's conjecture when $t = 5$ is "apex", that is, it consists of a planar graph with one additional vertex. Consequently, the 4CC implies Hadwiger's conjecture when $t = 5$, because it implies that apex graphs are 5-colourable.

3.3. From Peter Mihók's review of the paper.

The known Wagner theorem (1937) shows that the famous conjecture of Hadwiger (1943), "For every t ≥ 0, every loopless graph not contractible to $K_{t+1}$ is t-colourable'', is equivalent to the four-colour conjecture (4CC) when $t = 4$.

In this paper it is proved that the 4CC is equivalent to Hadwiger's conjecture for $t = 5$ as well. The authors reformulate the main result to avoid mention of the 4CC in the following way: A graph $G$ is said to be apex if $G−v$ is planar for some vertex $v$. They prove that every minimal counterexample to Hadwiger's conjecture when $t = 5$ is apex.

Their extensive and very stimulating proof is organised, as mentioned, to apply to all graphs satisfying the hypotheses of a Jorgensen conjecture, that every 6-connected graph with no $K_{6}$-minor is apex; however, the conjecture still remains open.

4.1. The Ostrowski Prize.

The Ostrowski Foundation was established by Alexander Markowich Ostrowski, for many years a professor at the University of Basel. He left his entire estate to the foundation and stipulated that the income should provide a prize for outstanding recent achievements in pure mathematics and the foundations of numerical mathematics. Every second year the Ostrowski Foundation provides the Ostrowski Prize for recent outstanding achievements in pure mathematics and in the foundations of numerical mathematics

Since 1989 this prize has been awarded, in general, every other year.

4.2. The 2003 Ostrowski Prize.

The prize jury consists of representatives from the universities of Basel, Jerusalem, and Waterloo and from the academies of Denmark and the Netherlands. For the 2003 prize, the jury members are: Joram Lindenstrauss, David Masser, Cameron Stewart, Carsten Thomassen, and Robert Tijdeman.

4.3. Citation prepared by the jury of the Ostrowski Prize.

Paul Seymour was born in 1950 in England, obtained his D.Phil. from the University of Oxford in 1975, and is currently a professor of mathematics at Princeton University. He received the George Pólya Prize in 1983 and the Fulkerson Prize in 1979 and 1994, the second time jointly with Neil Robertson and Robin Thomas. In 1994 he gave a plenary lecture at the International Congress of Mathematicians.

Paul Seymour has enriched mathematics with a number of spectacular results. His work is known not only by all discrete mathematicians but also by most theoretical computer scientists.

For instance, Seymour gave a precise characterisation of totally unimodular matrices, a result which is one of the deepest in the theory of matroids. With Robertson and Thomas he characterised completely the graphs which cannot be embedded in three-space without two cycles being linked and also solved Pólya's permanent problem from 1913 and the next open case (one past the four-colour theorem) of Hadwiger's conjecture of 1943. Robertson, Sanders, Seymour, and Thomas gave a new and simpler proof of the four-colour theorem of Appel and Haken. Further, in a sequence of papers with Robertson he proved that, for every infinite collection of finite graphs, there is always one which can be obtained from another by deleting and contracting edges. Their work provides polynomially bounded algorithms for all those graph properties which are closed under deleting or contracting edges.

Recently Seymour and his student Chudnovsky combined their work with that of Seymour and his close collaborators Robertson and Thomas in order to prove the strong perfect graph conjecture of Berge. Berge's conjecture had stood since 1961 and was one of the most important open problems in graph theory. The chromatic number of a graph $G$ is the minimum number of colours needed to colour the vertices of $G$ so that adjacent vertices have different colours. The clique number of $G$ is the largest number of pairwise adjacent vertices of $G$. Those graphs for which the two numbers are equal for all induced subgraphs are known as perfect graphs. A hole of a graph is a chordless cycle of length at least four, and an antihole is the complement of such a cycle. Berge conjectured that a graph is perfect if and only if it contains no odd hole or antihole. The proof by Chudnovsky, Robertson, Seymour, and Thomas of Berge's conjecture is a profound contribution to the subject of combinatorial mathematics.

5.1. The 2004 G Polya Prize.

The 2004 G Polya Prize was awarded jointly to Neil Robertson and Paul Seymour. The Selection Committee was William J Cook (Chair), Fan Chung Graham, Jerrold Griggs, Laszlo Lovasz and Peter Winkler.

6.1. The 2006 Fulkerson Prize.

The selection committee for the 2006 Fulkerson Prize consisted of Noga Alon, William Cunningham, and Michel Goemans (chair).

One of the three 2006 D R Fulkerson Prizes was awarded to Neil Robertson and Paul D Seymour for their joint paper 'Graph Minors. XX. Wagner's conjecture', Journal of Combinatorial Theory, Series B 92 (2) 2004, 325-357.

6.2. Announcement of the Fulkerson Prize Committee.

Kuratowski's theorem says that a graph is planar if and only if it does not contain $K_{5}$ or $K_{3,3}$ as a minor. Several other excluded minor characterisations are known, and Wagner conjectured that any minor-closed graph property can be characterised by a finite list of excluded minors. Restated, this says that for any infinite family of finite graphs, one of its members is a minor of another one. In a remarkable tour de force, Robertson and Seymour proved Wagner's conjecture, and this paper appeared as part 20 of their monumental work on the theory of graph minors. Their proof of the Graph Minor Theorem required the development of many graph theoretic concepts, such as linkages and tree-width. This is a spectacular achievement in graph theory with far reaching consequences. It shows, for example, that embeddability in any fixed surface can be characterised by a finite list of excluded minors, or that the disjoint paths problem can be solved in polynomial time for a fixed number of terminals.

Neil Robertson is in the Department of Mathematics at the Ohio State University. Paul D Seymour is in the Department of Mathematics at Princeton University.

6.3. Abstract of the winning paper.

We prove Wagner's conjecture, that for every infinite set of finite graphs, one of its members is isomorphic to a minor of another.

6.4. From Dan Steven Archdeacon's review of the paper.

This paper is the culmination of a series investigating graph minors. In this work the authors prove Wagner's conjecture: every infinite set of finite graphs contains one graph that is isomorphic to a minor of another. As a corollary: for every class of finite graphs closed under taking minors, there is a finite list of excluded minors characterising that class.

The result is of fundamental importance in graph theory.

7.1. From the Department of Combinatorics and Optimisation, University of Waterloo.

Professor Paul Seymour received an honorary Doctor of Mathematics (DMath) at the University of Waterloo's Fall Convocation.

Paul is a mathematician whose research has had profound impact in mathematics and theoretical computer science. He is the world's leading expert in the area of structural combinatorics. He has the unique distinction of having been awarded the Fulkerson Prize on three occasions. He has also received several other prestigious awards, including the Polya Prize (twice) and the Ostrowski Prize.

His many remarkable research accomplishments include the decomposition of regular matroids, the proof of the Strong Perfect Graph Theorem, and a shorter, more robust, proof of the Four Colour Theorem. However his work on the Graph Minors Project, joint with Neil Robertson, is undoubtedly his crowning achievement. The theorem states that "in any infinite sequence of graphs, there are two graphs one containing the other as a minor".

Paul obtained his doctorate from Oxford University in 1975 and is now Professor of Mathematics at Princeton University. He has maintained close connections with the University of Waterloo having worked here, as a Visiting Research Associate, in 1978-79, and then holding an Adjunct Professorship here from 1988 to 1993.

8.1. The 2009 Fulkerson Prize.

The 2009 Delbert Ray Fulkerson Prizes were presented at the 20th International Symposium on Mathematical Programming, held 23 August to 28 August 2009, in Chicago.

One of the three 2009 D R Fulkerson Prizes was awarded to Maria Chudnovsky, Neil Robertson, Paul D Seymour and Robin Thomas for their joint paper 'The strong perfect graph theorem', Annals of Mathematics (2) 164 (1) (2006), 51-229.

8.2. Announcement of the Fulkerson Prize Committee.

Claude Berge introduced the class of perfect graphs in 1960, together with a possible characterisation in terms of forbidden subgraphs. The resolution of Berge's strong perfect graph conjecture quickly became one of the most sought-after goals in graph theory. The pursuit of the conjecture brought together four important elements: vertex colourings, stable sets, cliques, and clique covers. Moreover, D R Fulkerson established connections between perfect graphs and integer programming through his theory of antiblocking polyhedra. A graph is called perfect if for every induced subgraph H the clique-covering number of H is equal to the cardinality of its largest stable set. The strong perfect graph conjecture states that a graph is perfect if and only if neither it nor its complement contains, as an induced subgraph, an odd circuit having at least five edges. The elegance and simplicity of this possible characterisation led to a great body of work in the literature, culminating in the proof by Chudnovsky, Robertson, Seymour, and Thomas, which was announced in May 2002, just one month before Berge passed away. The long, difficult, and creative proof by Chudnovsky and her colleagues is one of the great achievements in discrete mathematics.

Maria Chudnovsky is in the Department of Mathematics at Princeton University. Neil Robertson is in the Department of Mathematics at the Ohio State University. Paul Seymour is in the Department of Mathematics and the Program in Applied and Computational Mathematics at Princeton University. Robin Thomas is in the School of Mathematics at the Georgia Institute of Technology.

8.3. Abstract of the winning paper.

A graph $G$ is perfect if for every induced subgraph $H$, the chromatic number of $H$ equals the size of the largest complete subgraph of $H$, and $G$ is Berge if no induced subgraph of $G$ is an odd cycle of length at least five or the complement of one.

The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuéjols and Vušković - that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge's conjecture cannot have either of these properties).

In this paper we prove both of these conjectures.

8.4. From Carsten Thomassen's review of the paper.

The result of this paper, known as the strong perfect graph theorem, is no doubt one of the most important ones in recent mathematics. It was formulated as a conjecture by Claude Berge around 1960 and it is easy to state. The chromatic number of a graph is clearly greater than or equal to its clique number (the number of vertices in a largest complete subgraph). If we have equality, not just for the graph itself, but also for every induced subgraph, then the graph is called perfect. An odd cycle of length at least 5 and its complement are examples of imperfect graphs. The strong perfect graph conjecture (now theorem) asserts that a graph is perfect if and only if it does not contain an induced subgraph which is either an odd cycle or the complement of an odd cycle. Clearly, this implies the weaker conjecture, called the perfect graph conjecture and also formulated around 1960 by Berge, that a graph is perfect if and only if its complement is perfect. Fulkerson attacked the weaker conjecture by his powerful theory of blocking and antiblocking polyhedra and reduced it to what has become known as the replication lemma which was proved by L Lovász in 1972.

The two conjectures of Berge stimulated a considerable amount of research, not only because of their beauty, but also because of their role in various other problems. Berge himself was motivated by the so-called Shannon capacity in coding theory. Perfect graphs also appear in connection with graph entropy, also motivated by coding. The integer program is notoriously hard (NP-hard). It can be solved as a linear program (which is possible in polynomial time) provided one can be sure that the linear program has only integer solutions. The problem of deciding this question turns out to be one about perfect graphs.

Many results on perfect graphs say that a certain class of graphs are perfect. There are (at least) 96 such classes. The following five classes, which are called basic, are particularly relevant for the strong perfect graph theorem: The bipartite graphs are clearly perfect, and the line graphs of the bipartite are perfect by an elementary but important and classical result known as König's theorem. By Lovász's theorem, we obtain two other classes by taking complements. Finally, there is a class consisting of graphs obtained by doubling each vertex of a split graph. These graphs are therefore called double split graphs. A recent conjecture of M Conforti, G Cornuéjols and K Vušković says that every graph satisfying the condition in Berge's conjecture either belongs to one of the five basic classes, or else it has a certain property which has been called a "decomposition" or a "structural fault". There are four such properties in the theorem: a 2-join, a 2-join of the complement, a proper homogeneous pair, and a balanced skew partition. The important thing about these properties is that none of them can be satisfied in a smallest counterexample to the strong perfect graph conjecture. The present paper proves the conjecture of Conforti, Cornuéjols and Vušković and hence also the strong perfect graph conjecture. The proof is deep and complicated, over 150 pages.

9.1. Paul Seymour awarded honorary doctorate.

Professor Paul Seymour was awarded an Honorary Doctorate from the Technical University of Denmark at their commencement on 3 May 2013. It was held in the in the presence of Her Majesty Queen Margrethe II and more than 4,000 guests.

9.2. Citation for Paul Seymour's honorary doctorate.

The Academic Council of the Technical University of Denmark decided that the title should be awarded to:

Professor Paul Seymour, for his contribution to mathematics at the highest level, including his work with graph theory, which lays the foundations for everything related to networks - traffic networks and social networks, for example. Moreover, Professor Paul Seymour has developed the graph minor theorem that gave its name to the Robertson-Seymour theory. Professor Seymour's long partnership with the Technical University of Denmark underlines the university's focus on engineer programmes with a solid mathematical-scientific basis.

10.1. Paul Seymour receives the Commemorative Medal.

On Tuesday 27 August, one of the most prominent mathematicians of the present day, Paul Seymour (69), who is based at Princeton University, came to Comenius University to receive a Commemorative Medal. Seymour, originally from Britain, is an elite academic in discrete mathematics, combinatorics, and graph theory.

10.2. Citation for Paul Seymour.

Paul Seymour has co-authored a long and revolutionary series of articles about minors in graph theory which has determined the direction of research in this area. "If there was a Nobel Prize for mathematics, then Paul Seymour would definitely be a hot candidate," said the vice-dean of the Faculty of Mathematics, Physics, and Informatics, Róbert Jajcay.

Perhaps his most widely known work is his contribution to the simplification of proof of the four-colour theorem. This theorem states that every planar map can be coloured using a maximum of four colours so that no two countries with a common border (not just one point) will have the same colour, thus allowing political maps, for instance, to show colour variation.

"Anyone who attempts to colour in such a map will quickly see that four colours are enough for all real maps with a reasonable number of countries. By contrast, it is surprisingly difficult to prove the general application of this theory and that there does not exist a certain complicated map where more colours need to be used," explains Jajcay. It is important to find an explanation that covers all possible maps, even those that have never been thought of before. The number of possible maps is infinite.

Seymour has worked at the University of Oxford, the University of Waterloo, and Ohio State University. He holds two honorary doctorates and a number of awards in mathematics, including the Ostrowski Prize, the George Pólya Prize, and the Fulkerson Prize.

At 2:30 pm on Tuesday, Seymour receives the university's Commemorative Medal in the Auditorium from the university's rector, Marek Števček. "It is an honour for us to host the world's leaders in combinatorics in the 100th year of our university. Professor Seymour is a true inspiration among them and for those beyond the world of mathematical professionals," the rector said.

Paul Seymour's visit is associated with his speech at the 2019 Eurocomb conference (a European conference on combinatorics, graph theory, and their applications), which takes place this year at Comenius University in Bratislava. The conference takes place every two years in a different European city and represents a forum for experts to exchange the latest knowledge in the field. Almost 200 mathematicians from around the world will be present, among them other top world experts.

11.1. Paul Seymour's entry in the Fellows Directory.

Professor Paul Seymour FRS

Paul Seymour is a mathematician working in graph theory, the study of network interconnections. He has been awarded several prizes, including the Ostrowski Prize, and the D R Fulkerson Prize (four times). Here are two of his most important results.

With Neil Robertson, Seymour proved the 'graph minors structure theorem', which says that for any graph, all graphs that do not contain it as a 'minor' can more-or-less be drawn on a surface of bounded genus. This has had many applications: for instance, it implied that in any infinite set of graphs, one of them contains another as a minor.

With Maria Chudnovsky, Neil Robertson and Robin Thomas, Seymour proved the 'strong perfect graph theorem'. 'Colouring' a graph means giving each vertex a colour different from the colours of its neighbours, and the game is to use the fewest possible number of colours. If the graph contains, say, ten vertices all joined to one another, then at least ten colours will be needed, and perhaps more: but sometimes the maximum number of vertices all joined to one another is the right answer. They characterised when this is true, which was a famous, long-standing and much-studied question.

Paul Seymour is the Alfred Baldwin Dod Professor of Mathematics in the Department of Mathematics at Princeton University.

11.2. Princeton announcement.

Paul Seymour was elected as a Fellow of the Royal Society on 10 May 2022. Seymour is the recipient of many prizes, including the Ostrowski Prize, and the D R Fulkerson Prize (four times).

The Royal Society was founded in the 1660s to promote "the development and use of science for the benefit of humanity." It is made up of approximately 1,600 of the most eminent scientists, engineers and technologists from the United Kingdom and the Commonwealth. Fellows and foreign members are elected for life through a peer review process on the basis of excellence in science. Each year up to 52 fellows and up to 10 foreign members are elected from a group of around 700 candidates who are proposed by the existing fellowship.

12.1. The Ceremony.

The Ceremony was held in the City Hall of Lyon at 5:30 pm on Thursday 23 June 2022.

Jean-François Pinton, President of the École normale supérieure de Lyon, hosted the official ceremony during which Pr Abhijit Banerjee - Professor of Economics at Massachusetts Institute of Technology, 2019 Bank of Sweden Prize in Economic Sciences in Memory of Alfred Nobel - and Paul Seymour - Professor of Mathematics at Princeton University, pioneer in discrete mathematics and theoretical computer science - was bestowed the diploma of Doctor Honoris Causa of École normale supérieure de Lyon.

12.2. Biography of Paul Seymour.

Paul Seymour is currently a professor of mathematics at Princeton University in the United States.

He studied at Oxford University, where in 1975 he defended a thesis in mathematics - Matroids, hypergraphs and the max-flow min-cut theorem - under the supervision of Aubrey William Ingleton.

From 1974 to 1976 he was a College Research Fellow at the University College of Swansea, then a Junior Research Fellow from 1976 to 1980 at Merton College, Oxford, and in 1978-1979 at the University of Waterloo.

He became an Associate and then a Full professor at Ohio State University in Columbus between 1980 and 1983 and initiated a fruitful collaboration with Neil Robertson that continued for many years. From 1983 to 1996, he worked at Bellcore in Morristown. In parallel, he was Adjunct Professor at Rutgers University from 1984 to 1987 and at the University of Waterloo from 1988 to 1993. He became a Professor at Princeton University in 1996 and is also editor-in-chief, with Carsten Thomassen, from the Journal of Graph Theory.

Paul Seymour made several notable advances in mathematics and theoretical computer science, on regular matroids, graph mining (Robertson-Seymour theorem), the strong perfect graph theorem, and Hadwiger's conjecture. One of his best-known works is his contribution to simplifying the proof of the four-colour theorem. This theorem states that every planar map can be coloured using a maximum of four colours so that two countries sharing a border do not have the same colour.

A pioneer in discrete mathematics and theoretical computer science - particularly graph theory, optimisation, and algorithms - Paul Seymour has an exemplary career, and the impact of his work has earned him extensive international recognition.