Fulkerson Prize
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 $1,500 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. 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 is defined to be the print publication year (for volumes that appear in print) or the electronic publication year (for volumes that appear only in electronic form). Extended abstracts, 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 reflects that the value of fundamental work cannot always be immediately assessed. The prizes will be awarded for single papers, not series of papers or books; 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 in these areas is often connected to practical applications, evaluation will be based solely on the mathematical quality and significance of the work. The Prize Committee will have two members appointed by the Chair of the MOS and one member appointed by the President of the American Mathematical Society. Committee members will serve for at most two rounds of awards, with overlapping terms whenever possible to ensure continuity. One of the initial Mathematical Optimization Society appointees will serve as the first chair of the committee. Subsequent chairs will be selected by the Prize Committee from among its members and should, whenever possible, be veterans of the previous round of awards. The Prize Committee will develop its own procedures for soliciting and identifying papers of interest, taking care not to overlook the work of young or relatively unknown mathematicians. The call for nominations for the Fulkerson Prize is Now Open . We invite eligible nominations and encourage interested nominators to review the requirements, submission instructions, and important deadlines on the official Call for Nominations page . Winner Gaussian Cooling and O(n³) Algorithms for Volume and Gaussian Volume SIAM Journal on Computing, Vol. 47, 2018. Ben Cousins Santosh Vempala The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture Advances in Mathematics, Vol. 392, 2021. Nathan Keller Noam Lifshitz Equiangular lines with a fixed angle Annals of Mathematics, Vol. 194, 2021. Zilin Jiang Jonathan Tidor Yuan Yao Shengtong Zhang Yufei Zhao Winner Proof of the 1-factorization and Hamilton decomposition conjectures Memoirs of the AMS, vol. 244, no. 1154 (2016). Béla Csaba Daniela Kühn Allan Lo Deryk Osthus Andrew Treglown Complexity of Counting CSP with Complex Weights JACM, vol. 64, no. 3 (2017). Jin-Yi Cai Xi Chen Deterministic Edge Connectivity in Near-Linear Time JACM, vol. 66, no. 1 (2018). Ken-Ichi Kawarabayashi Mikkel Thorup Winner The chromatic thresholds of graphs Adv. Math. 235 (2013), 261–295. Peter Allen Julia Böttcher Simon Griffiths Yoshiharu Kohayakawa Robert Morris The Matching Polytope has Exponential Extension Complexity. JACM 64(6): 41:1–41:19 (2017). Thomas Rothvoß Winner A Counterexample to the Hirsch Conjecture Annals of Mathematics, 2012. Francisco Santos Winner Expander flows, geometric embeddings and graph partitioning JACM 56 (2009), 1–37. Sanjeev Arora Satish Rao Umesh Vazirani Factors in random graphs Random Structures and Algorithms 33 (2008), 1–28. Anders Johansson Jeff Kahn Van Vu Limits of dense graph sequences JCT B 96 (2006), 933–957. Lászlo Lovász Balázs Szegedy Winner The strong perfect graph theorem Annals of Mathematics 164 (2006), 51–229. Maria Chudnovsky Neil Robertson Paul Seymour Robin Thomas Shared one prize A proof of the Kepler conjecture Annals of Mathematics 162 (2005), 1063–1183. Thomas C. Hales Sphere Packings, V. Pentahedral Prisms Discrete & Computational Geometry 36 (2006), 167–204. Samuel P. Ferguson Winner Smoothed analysis of algorithms JACM 51 (2004), 385–463. Daniel Spielman Shang-Hua Teng Winner PRIMES is in P Annals of Mathematics 160 (2004), 781–793. Manindra Agrawal Neeraj Kayal Nitin Saxena A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries JACM 51 (2004), 671–697. Mark Jerrum Alistair Sinclair Eric Vigoda Graph Minors XX. Wagner's conjecture JCT B 92 (2004), 325–357. Neil Robertson Paul D. Seymour Winner The Excluded Minors for GF(4)-Representable Matroids JCT B 79 (2000), 247–299. Jim F. Geelen A. M. H. Gerards Ajai Kapoor A characterization of weakly bipartite graphs JCT B 83 (2001), 112–168. Bertrand Guenin Shared one prize A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions JACM 48 (2001), 761–777. Satoru Iwata Lisa Fleischer Satoru Fujishige A combinatorial algorithm minimizing submodular functions in strongly polynomial time JCT B 80 (2000), 346–355. Alexander Schrijver Winner Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming JACM 42 (1995), 1115–1145. Michel X. Goemans David P. Williamson Decomposition of balanced matrices JCT B 77 (1999), 292–406. Michele Conforti Gérard Cornuéljols M. R. Rao Winner The Ramsey Number R(3,t) has order of magnitude t²/log t Random Structures and Algorithms 7 (1995), 173–207. Jeong Han Kim Winner Homology of smooth splines: generic triangulations and a conjecture of Strang Trans. AMS 310 (1988), 325–340. Lou Billera Hadwiger's conjecture for K6-free graphs Combinatorica 13 (1993), 279–361. Neil Robertson Paul D. Seymour Robin Thomas Upper bounds for the diameter and height of graphs of convex polyhedra Discrete & Computational Geometry 8 (1992), 363–372. Gil Kalai Winner The width-length inequality and degenerate projective planes DIMACS Series, Vol. 1 (1990), 101–105. Alfred Lehman The universality theorems… Lecture Notes in Mathematics 1346 (1988), 527–544. Nikolai E. Mnev A random polynomial time algorithm for approximating the volume of convex bodies JACM 38 (1991), 1–17. Martin Dyer Alan Frieze Ravi Kannan Winner A strongly polynomial minimum cost circulation algorithm Combinatorica 5 (1985), 247–256. Éva Tardos A new polynomial-time algorithm for linear programming Combinatorica 4 (1984), 373–395. Narendra Karmarkar Winner Roth's estimate of the discrepancy of integer sequences is nearly sharp Combinatorica 1 (1981), 319–325. Jozsef Beck Integer programming with a fixed number of variables Math. of OR 8 (1983), 538–548. Hendrik W. Lenstra Jr Isomorphism of graphs of bounded valence can be tested in polynomial time JCSS 25 (1982), 42–65. Eugene M. Luks Shared one prize A polynomial algorithm in linear programming Dokl. Akad. Nauk SSR 244 (1979) Leonid G. Khachiyan Informational complexity… Ekonomika i Mat. Metody 12 (1976). David B. Iudin Arkadi S. Nemirovskii Shared one prize The solution of van der Waerden's problem for permanents Dokl. Akad. Sci. SSSR 258 (1981) G. P. Egorychev A proof of the van der Waerden conjecture… Mat. Zametiki 29 (1981). D. I. Falikman Winner The ellipsoid method… Combinatorica 1 (1981), 169–197. Martin Grötschel Lászlo Lovász Alexander Schrijver Winner Every planar map is four-colorable, Part I: Discharging Illinois J. Math 21 (1977), 429–490. Kenneth Appel Wolfgang Haken On the computational complexity of combinatorial problems Networks 5 (1975), 45–68. Richard M. Karp The matroids with the max-flow min-cut property JCT B 23 (1977), 189–222. Paul D. Seymour