The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society and the American Mathematical Society. Beginning in 1979, up to three awards of $750 each will be presented at each (triennial) International Symposium on Mathematical Programming; they will be paid out of a memorial fund administered by the American Mathematical Society that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. Beginning in 1994, the amount of each award is $1,500.
Guidelines
To be eligible, a paper should be the final publication of the main result(s) and should have been published in a recognized journal, or in a comparable, well-refereed volume intended to publish final publications only, during the six calendar years preceding the year of the International Symposium on Mathematical Programming. The publication year for the paper will be defined to be the print publication year, for any volume that appears in print, or the electronic publication year, for any volume that appears only in electronic form. Extended abstracts and prepublications, and articles published in journals, journal sections or proceedings that are intended to publish nonfinal papers, are not included. The extended period of six years is in recognition of the fact that the value of fundamental work cannot always be immediately assessed. The prizes will be given for single papers, not series of papers or books, and in the event of joint authorship the prize will be divided.
The term “discrete mathematics” is intended to include graph theory, networks, mathematical optimization, applied combinatorics, and related subjects. While research work in these areas is usually not far removed from practical applications, the judging of papers will be based on their mathematical quality and significance.
The Prize Committee
The Prize Committee for the awards will have two members appointed by the Chair of the MOS and one member appointed by the President of the American Mathematical Society. The committee members will serve for at most two rounds of awards, with terms overlapping where possible for the sake of continuity. One of the initial Mathematical Optimization Society appointees will be the first chair of the committee; subsequent chairs will be chosen by the Prize Committee from among its members and should whenever possible be veterans of the previous round of awards. The Prize Committee will devise its own procedures for acquiring nominations or otherwise searching out papers of interest, taking pains, however, not to overlook the work of young, relatively unknown mathematicians.
2024 Fulkerson Prize Citations
- Ben Cousins and Santosh Vempala, “Gaussian Cooling and O*(n³) Algorithms for Volume and Gaussian Volume”, SIAM Journal on Computing, Vol. 47, 2018.
Computing the volume of a convex body is an ancient challenge. Cousins and Vempala develop a fast algorithm that approximates the volume of a well-rounded convex body while querying membership of a cubic number of points, and also present the fastest algorithms for integrating and sampling from a Gaussian measure restricted to a convex body. The impact of the ideas goes far beyond the two core problems addressed.
- Nathan Keller and Noam Lifshitz, “The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture”, Advances in Mathematics, Vol. 392, 2021.
The authors give a new approach for solving Turán-type problems, which concern the maximum number of edges a hypergraph can have without containing certain expansions of a given forbidden substructure. The junta method approximates these hypergraphs by juntas, and the authors successfully apply it to the Erdős-Chvátal simplex conjecture, the Erdős-Sós forbidding one intersection problem, and the Frankl-Füredi special simplex problem.
- Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao, “Equiangular lines with a fixed angle”, Annals of Mathematics, Vol. 194, 2021.
The authors solve a combinatorial geometry problem that has received considerable attention since the 1960s: determine the maximum number of lines in d-dimensional space such that the angle between every pair is exactly θ. For fixed θ and large d, the authors provide a sharp bound. The proofs combine combinatorial ideas with tools from spectral graph theory in a clever, original and elegant way.
Past Winners of the Fulkerson Prize
| Year | Winners | Selection Committee |
| 1979 |
Kenneth Appel and Wolfgang Haken, "Every planar map is four-colorable, Part I: Discharging", Illinois J. Math 21 (1977), 429-490. Richard M. Karp, "On the computational complexity of combinatorial problems", Networks 5 (1975), 45-68. Paul D. Seymour, "The matroids with the max-flow min-cut property", Journal of Combinatorial Theory B 23 (1977), 189-222. |
R. Graham, V. Klee, A. Tucker |
| 1982 |
Shared one prize: Shared one prize: Martin Grötschel, Lászlo Lovás, and Alexander Schrijver, "The
ellipsoid method and its consequences in combinatorial optimization", Combinatorica 1
(1981), 169-197. |
R. Graham, R. Karp, V. Klee |
| 1985 |
Jozsef Beck, "Roth's estimate of the discrepancy of integer sequences is nearly sharp", Combinatorica 1 (1981), 319-325. Hendrik W. Lenstra, Jr., "Integer programming with a fixed number of variables", Mathematics of Operations Research 8 (1983), 538-548. Eugene M. Luks, "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences 25 (1982), 42-65. |
A. Hoffman, R. Karp, L. Lovasz |
| 1988 |
Éva Tardos, "A strongly polynomial minimum cost circulation algorithm", Combinatorica 5 (1985), 247-256. Narendra Karmarkar, "A new polynomial-time algorithm for linear programming", Combinatorica 4 (1984), 373-395. |
M. Grötschel, M. Padberg, G. Rota |
| 1991 |
Alfred Lehman, "The width-length inequality and degenerate projective planes", in W. Cook and P.D. Seymour (eds.), "Polyhedral Combinatorics", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1, 1990, AMS, 101-105. Nikolai E. Mnev, "The universality theorems on the classification problem of configuration varieties and convex polytope varieties" in: O. Ya. Viro (ed.), Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics 1346, Springer-Verlag, Berlin, 1988, 527-544. Martin Dyer, Alan Frieze, and Ravi Kannan, "A random polynomial time algorithm for approximating the volume of convex bodies", Journal of the ACM 38 (1991), 1-17. |
L. Billera, M. Grötschel, P. Seymour |
| 1994 |
Lou Billera, "Homology of smooth splines: generic triangulations and a conjecture of Strang", Transactions of the American Mathematical Society 310 (1988), 325-340. Neil Robertson, Paul D. Seymour, and Robin Thomas, "Hadwiger's conjecture for K6-free graphs", Combinatorica 13 (1993), 279-361. Gil Kalai, "Upper bounds for the diameter and height of graphs of convex polyhedra", Discrete and Computational Geometry 8 (1992), 363-372. |
A. Schrijver, A. Hoffman, É. Tardos |
| 1997 |
Jeong Han Kim, "The Ramsey Number R(3,t) has order of magnitude t^2/log
t", Random Structures and Algorithms 7 (1995), 173-207. |
R. Graham, R. Kannan, É. Tardos |
| 2000 |
Michel X. Goemans and David P. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM 42 (1995), 1115-1145. Michele Conforti, Gérard Cornuéljols, M. R. Rao, "Decomposition of balanced matrices", Journal of Combinatorial Theory B 77 (1999), 292-406. |
R. Kannan, R. Graham, W. Cook |
| 2003 |
Jim F. Geelen, A. M. H. Gerards, Ajai Kapoor, "The Excluded Minors for GF(4)-Representable Matroids", Journal of Combinatorial Theory B 79 (2000), 247-299. Bertrand Guenin, "A characterization of weakly bipartite graphs", Journal of Combinatorial Theory B 83 (2001) 112-168. Shared one prize: |
D. Williamson, G. Cornuejols, A. Odlyzko |
| 2006 |
Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160, No. 2 (2004), Pages 781-793. Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", J. ACM 51, No. 4 (2004), Pages 671-697. Neil Robertson and Paul D. Seymour, "Graph Minors XX. Wagner's conjecture", Journal of Combinatorial Theory Series B 92, No 2, (2004), Pages 325-357. |
M. Goemans, N. Alon, W. Cunningham |
| 2009 |
Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas, "The strong perfect graph theorem", Annals of Mathematics 164 (2006) 51-229. Shared one prize: Daniel Spielman and Shang-Hua Teng, "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", Journal of the ACM 51 (2004) 385-463. |
W. Cook, M. Goemans, D. Kleitman |
| 2012 |
Sanjeev Arora, Satish Rao, and Umesh Vazirani,
Anders Johansson, Jeff Kahn, and Van Vu,
Lászlo Lovász and Balázs Szegedy, |
K. Aardal P. Seymour R. Stanley |
| 2015 |
Francisco Santos, |
M. Conforti F. Eisenbrand E. Schulte |
| 2018 |
Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, Robert Morris, Thomas Rothvoß, |
M. Chudnovsky F. Eisenbrand M. Grötschel |
| 2021 |
Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown, Jin-Yi Cai and Xi Chen, Ken-Ichi Kawarabayashi and Mikkel Thorup, |
Gérard Cornuéjols Éva Czabarka Dan Spielman |
| 2024 |
Ben Cousins and Santosh Vempala, Nathan Keller and Noam Lifshitz, Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei
Zhao |
Julia Böttcher Rosa Orellana Dan Spielman |