Fulkerson Prize facts for kids

The Fulkerson Prize is a special award for amazing research papers in discrete mathematics. This area of math deals with things that can be counted, like graphs and networks.

The prize is given out by two big groups: the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards are given out every three years. Each winner receives $1,500.

The award started in 1979. It honors Delbert Ray Fulkerson, a brilliant mathematician. His friends created a fund to encourage new discoveries in math, especially in areas he worked on. Today, the prizes are supported by a special fund managed by the MOS.

Who Won the Fulkerson Prize?

The Fulkerson Prize celebrates important breakthroughs in discrete mathematics. Here are some of the talented mathematicians who have won this award:

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 states that any map can be colored with only four colors so that no two neighboring regions have the same color.
• Paul Seymour for expanding a key idea called the max-flow min-cut theorem. This theorem helps solve problems about flows in networks.

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, which is about finding the best solution among many choices.
• G. P. Egorychev and D. I. Falikman for proving a math idea called van der Waerden's conjecture.

1985 Winners

• Jozsef Beck for his work on discrepancy theory. This area of math looks at 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 complex.

1988 Winners

• Éva Tardos for finding ways to calculate the cheapest flow in networks very quickly.
• Narendra Karmarkar for his new method called Karmarkar's algorithm, which helps solve linear programming problems more efficiently.

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 types of matrices (grids of numbers) related to perfect graphs.
• Nikolai E. Mnev for his theorem showing that many complex shapes can be linked to mathematical structures called oriented matroids.

1994 Winners

• Louis Billera for finding ways to describe spaces of functions over geometric shapes.
• Gil Kalai for making progress on the Hirsch conjecture. This conjecture is about how many steps it takes to go from one corner to another on a geometric shape called a polytope.
• Neil Robertson, Paul Seymour and Robin Thomas for their work on a part of Hadwiger's conjecture, which is about coloring graphs.

1997 Winners

• Jeong Han Kim for figuring out how fast certain numbers, called Ramsey numbers, grow. Ramsey numbers are about finding patterns in large groups.

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 called balanced 0-1 matrices.

2003 Winners

• J. F. Geelen, A. M. H. Gerards and A. Kapoor for their work on Rota's conjecture, which is about how certain mathematical structures called matroid minors behave.
• Bertrand Guenin for describing a type of graph called weakly bipartite graphs.
• 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 test quickly tells if a very large number is a prime number.
• Mark Jerrum, Alistair Sinclair and Eric Vigoda, for finding a way to estimate the permanent of a matrix.
• Neil Robertson and Paul Seymour, for their Robertson–Seymour theorem. This theorem shows how graphs can be ordered based on their smaller parts.

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.
• Daniel A. Spielman and Shang-Hua Teng, for their work on smoothed analysis of algorithms, which helps explain why some algorithms 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) to take up the least space.

2012 Winners

• Sanjeev Arora, Satish Rao, and Umesh Vazirani for improving how we find graph separators. These are small sets of vertices that can split a graph into smaller pieces.
• Anders Johansson, Jeff Kahn, and Van H. Vu for figuring out when a random graph can be completely covered by copies of a smaller graph.
• László Lovász and Balázs Szegedy for describing how often smaller graphs appear within sequences of dense graphs.

2015 Winners

• Francisco Santos Leal for finding an example that disproved the Hirsch conjecture.

2018 Winners

• Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and Julia Böttcher for their work on the "chromatic thresholds of graphs." This relates to coloring graphs.
• Thomas Rothvoss for his work on the extension complexity of the matching polytope. This helps in understanding how complex certain math problems are.

2021 Winners

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

Source: Mathematical Optimization Society official website.

See also

In Spanish: Premio Fulkerson para niños

• List of mathematics awards