Fulkerson Prize facts for kids

The Fulkerson Prize is a special award given to people who write amazing papers in discrete mathematics. This is a type of math that deals with things that can be counted, like graphs or networks, rather than smooth, continuous things. The prize is given out by two big math groups: the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards, each with $1,500, are given out every three years at a big meeting of the MOS. The prize was created to honor Delbert Ray Fulkerson, a famous mathematician, and to encourage new discoveries in math fields he worked on.

Who Won the Fulkerson Prize?

The Fulkerson Prize has been awarded to many brilliant mathematicians over the years. Here are some of the winners and what they achieved:

1979 Winners

• Richard M. Karp for organizing many important NP-complete problems. These are problems that are hard for computers to solve quickly.
• Kenneth Appel and Wolfgang Haken for proving the four color theorem. This theorem says you only need four colors to color any map so that no two neighboring regions have the same color.
• Paul Seymour for making the max-flow min-cut theorem work for more complex math structures called matroids.

1982 Winners

• D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grötschel, László Lovász and Alexander Schrijver for their work on the ellipsoid method. This method helps solve problems in linear programming and combinatorial optimization.
• G. P. Egorychev and D. I. Falikman for proving van der Waerden's conjecture. This was a long-standing math puzzle about matrices.

1985 Winners

• Jozsef Beck for his work on discrepancy theory, which deals with how evenly things can be spread out.
• H. W. Lenstra Jr. for using the geometry of numbers to solve certain math problems faster.
• Eugene M. Luks for creating a fast way to tell if two graphs are the same, especially for graphs that are not too complicated.

1988 Winners

• Éva Tardos for finding ways to calculate minimum cost circulations very quickly.
• Narendra Karmarkar for his new method, Karmarkar's algorithm, which made solving linear programming problems much faster.

1991 Winners

• Martin E. Dyer, Alan M. Frieze and Ravindran Kannan for using random walks to estimate the size of complex shapes.
• Alfred Lehman for his work on special matrices that are like perfect graphs.
• Nikolai E. Mnev for his theorem that connects abstract math ideas to real-world shapes.

1994 Winners

• Louis Billera for finding ways to describe spaces of functions over divided shapes.
• Gil Kalai for making progress on the Hirsch conjecture, a problem about the "diameter" of geometric shapes.
• Neil Robertson, Paul Seymour and Robin Thomas for their work on a part of Hadwiger's conjecture, another graph coloring problem.

1997 Winners

• Jeong Han Kim for figuring out how fast Ramsey numbers grow. These numbers are about finding patterns in large groups of things.

2000 Winners

• Michel X. Goemans and David P. Williamson for creating new ways to find good solutions to hard problems using semidefinite programming.
• Michele Conforti, Gérard Cornuéjols, and M. R. Rao for finding a fast way to recognize special types of matrices.

2003 Winners

• J. F. Geelen, A. M. H. Gerards and A. Kapoor for their work on Rota's conjecture, a big problem in matroid theory.
• Bertrand Guenin for describing certain types of graphs using "forbidden minors."
• Satoru Iwata, Lisa Fleischer, Satoru Fujishige, and Alexander Schrijver for showing that a type of math problem called submodular minimization can be solved very quickly.

2006 Winners

• Manindra Agrawal, Neeraj Kayal and Nitin Saxena, for creating the AKS primality test. This is a fast way to tell if a very large number is a prime number.
• Mark Jerrum, Alistair Sinclair and Eric Vigoda, for finding a way to quickly estimate a complex math value called the permanent.
• Neil Robertson and Paul Seymour, for their Robertson–Seymour theorem. This theorem shows how graphs can be organized based on their "minors."

2009 Winners

• Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, for proving the strong perfect graph theorem. This theorem helps us understand certain types of graphs better.
• Daniel A. Spielman and Shang-Hua Teng, for their "smoothed analysis" of algorithms, which helps explain why some computer programs work well in practice.
• Thomas C. Hales and Samuel P. Ferguson, for proving the Kepler conjecture. This conjecture is about the best way to stack spheres, like oranges in a pile.

2012 Winners

• Sanjeev Arora, Satish Rao, and Umesh Vazirani for improving how we find "graph separators," which are ways to divide graphs into smaller pieces.
• Anders Johansson, Jeff Kahn, and Van H. Vu for figuring out when a random graph can be completely covered by smaller, identical graphs.
• László Lovász and Balázs Szegedy for their work on understanding patterns in sequences of dense graphs.

2015 Winners

• Francisco Santos Leal for finding a counter-example to the Hirsch conjecture. This showed that the conjecture, which had been around for a long time, was not always true.

2018 Winners

• Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and Julia Böttcher for their paper on "The chromatic thresholds of graphs."
• Thomas Rothvoss for his work on the "extension complexity" of the matching polytope, a concept in optimization.

2021 Winners

• Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, and Andrew Treglown for proving important conjectures about how graphs can be divided into specific patterns.
• Jin-Yi Cai and Xi Chen for their work on the "Complexity of Counting CSP with Complex Weights," which is about how hard certain counting problems are for computers.
• Ken-Ichi Kawarabayashi and Mikkel Thorup for finding a very fast way to check how connected a graph is.

2024 Winners

• Ben Cousins and Santosh Vempala for their work on "Gaussian cooling" and faster algorithms for calculating volume.
• Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao for their paper on "Equiangular lines with a fixed angle."
• Nathan Keller and Noam Lifshitz for their "junta method for hypergraphs" and work on the Erdős–Chvátal simplex conjecture.

Source: Mathematical Optimization Society official website. American Mathematical Society official website.

See also

In Spanish: Premio Fulkerson para niños

• List of mathematics awards