Hubbry Logo
Fulkerson PrizeFulkerson PrizeMain
Open search
Fulkerson Prize
Community hub
Fulkerson Prize
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Fulkerson Prize
Fulkerson Prize
Fulkerson Prize
View on Wikipedia
from Wikipedia
Fulkerson Prize
Awarded forOutstanding papers in the area of discrete mathematics
CountryUnited States
Presented by
Reward$1,500
First award1979
Websitehttp://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize Edit this on Wikidata

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MOS.

Winners

[edit]

Source: Mathematical Optimization Society official website.[47]

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

Source: American Mathematical Society official website.[48]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Fulkerson Prize

View on Grokipedia
from Grokipedia
The Fulkerson Prize is a prestigious award given triennially for outstanding papers in the field of , encompassing areas such as , networks, , and applied . Sponsored jointly by the (AMS) and the Mathematical Optimization Society (MOS), it honors contributions judged on their mathematical quality and significance, with up to three prizes of $1,500 each awarded to authors of eligible publications. Established in 1979 through a memorial fund for Delbert Ray Fulkerson (1924–1976), a pioneering known for his foundational work in , network flow theory, and combinatorial analysis, the prize initially offered $750 and increased to $1,500 in 1994. Now supported by an endowment from the MOS, it recognizes single papers published in well-refereed journals or comparable volumes within the six calendar years preceding the International Symposium on Mathematical Programming, where the awards are presented; joint authors share the prize equally. Notable recipients include Kenneth Appel and Wolfgang Haken for their 1976 proof of the four-color theorem, Richard M. Karp for seminal work on , and Paul D. Seymour for advances in , highlighting the prize's role in advancing research. The award underscores the interdisciplinary impact of on fields like optimization and , fostering innovation through rigorous, published scholarship.

History

Establishment

The Fulkerson Prize was established in 1979 through a collaborative effort by the (AMS) and the Mathematical Programming Society (now known as the Mathematical Optimization Society, or MOS). The initiative stemmed from a memorial fund created by friends of Delbert Ray Fulkerson (1924–1976) following his death, with the AMS initially administering the fund to support awards in his honor. The prize's funding originated from this memorial fund, which was later transformed into an endowment managed by the MOS to ensure its long-term sustainability. This financial structure allowed for the recognition of exceptional contributions without reliance on ongoing external sponsorships. The primary motivation for creating the prize was to encourage mathematical excellence in the fields of research exemplified by Fulkerson's own contributions, particularly in , , and . By honoring groundbreaking papers in these areas, the award aimed to perpetuate the innovative spirit of Fulkerson's work at the and his academic collaborations. The inaugural awards were presented in 1979 at the International Symposium on Mathematical Programming (ISMP) in , recognizing papers published during the period leading up to that event. This debut aligned the prize with a major international forum for optimization and related disciplines, setting a precedent for its triennial presentation at subsequent ISMP gatherings.

Namesake and Legacy

Delbert Ray Fulkerson (1924–1976) was an American mathematician renowned for his foundational contributions to and . Born on August 14, 1924, in Tamms, , he earned his B.S. from in 1947, his M.S. from the University of in 1948, and his Ph.D. from the University of in 1951. Fulkerson spent much of his early career at the , joining its Mathematics Department in 1951 and working there until 1971, after which he joined as the Maxwell M. Upson Professor of Engineering until his death. He also served as a distinguished visitor at the University of in 1968 and as a visiting professor in 1971, fostering international collaboration in the field. Fulkerson's major contributions centered on network flows and , where he co-developed the and the , providing essential tools for solving optimization problems in capacitated networks. These advancements extended to practical applications in combinatorial analysis, including blocking sets and techniques that bridged theoretical with real-world . Alongside L. R. Ford Jr., he co-authored the seminal book Flows in Networks in 1962, which formalized network flow theory and remains a cornerstone text for researchers in the field. His work emphasized the utility of discrete structures in addressing complex systems, influencing subsequent developments in . The Fulkerson Prize, established in through a memorial fund created by his colleagues, honors his legacy by recognizing outstanding papers in , reflecting his focus on practical applications of combinatorial methods. Fulkerson's unsolved problems, such as the Berge–Fulkerson conjecture in matching theory—which posits that the all-ones vector in a 3-uniform can be expressed as a combination of incidence vectors of perfect matchings—continue to drive research in areas eligible for the award, underscoring his enduring influence on the field's open challenges.

Prize Details

Criteria and Scope

The Delbert Ray Fulkerson Prize recognizes outstanding papers in the area of , with the term "" interpreted broadly to encompass foundational and applied topics such as , networks, mathematical programming, applied , and applications to , including interdisciplinary extensions like and . This expansive scope highlights significant theoretical advances, novel methodologies, or impactful resolutions to longstanding problems within these domains, prioritizing contributions that demonstrate high mathematical quality and lasting significance. Eligibility for the prize is restricted to single papers—excluding series or books—that represent the final publication of their main results and have appeared in recognized, peer-reviewed journals or comparable well-refereed volumes during the six calendar years immediately preceding the award year. Single or multiple authors are permitted, with the prize amount divided equally among co-authors in cases of joint work, and there are no restrictions based on or institutional affiliation. Representative topics within this scope include network flows, , and , reflecting the prize's emphasis on rigorous, innovative work that advances the field's core principles. The broad interpretation of discrete mathematics in the prize criteria echoes the diverse legacy of Delbert Ray Fulkerson, whose research spanned optimization, , and combinatorial applications.

Frequency and Administration

The Fulkerson Prize is awarded triennially, with the schedule aligned to the International Symposium on Mathematical Programming (ISMP), where the prizes are presented. The award cycles occur every three years, beginning in 1979; following the 2024 presentation, the next opportunity will be in 2027. Each cycle allows for up to three awards, with a monetary value of $1,500 per recipient. The prize amount originated at $750 for awards from 1979 through 1991 and was increased to the current $1,500 starting with the 1994 cycle. The prize is jointly administered by the Mathematical Optimization Society (MOS) and the , who together oversee nominations, evaluation, and presentation. Funding is provided through an endowment managed by MOS, which was established from initial memorial contributions by Fulkerson's colleagues and friends. Over time, the administration has seen minor evolutions, including an increase in the prize value in 1994 and a name change for one sponsor from the Mathematical Programming Society to the Mathematical Optimization Society in 2010, while the core triennial structure and joint sponsorship have remained consistent.

Selection Process

Nomination Procedure

Nominations for the Fulkerson Prize are open to any individual, including authors, colleagues, or editors, and can be submitted electronically via the websites of the Mathematical Optimization Society (MOS) or the (AMS). The process involves sending materials to the chair of the Fulkerson Prize Committee, with deadlines typically set for February 15 of the award year, approximately six months prior to the International Symposium on Mathematical Programming (ISMP). Required nomination materials consist of a letter that includes a full reference to the nominated paper and a detailed of its mathematical quality and significance in . Eligible papers must represent final publications of their main results in recognized, well-refereed journals or comparable volumes, strictly limited to those appearing in the six calendar years preceding the ISMP—for example, January 2018 through December 2023 for the 2024 award. The Prize Committee devises its own procedures for soliciting and reviewing nominations while actively seeking to identify outstanding but potentially overlooked contributions, particularly those by young or relatively unknown mathematicians. This approach ensures broad consideration of impactful work in the field.

Evaluation and Committee

The Fulkerson Prize selection committee consists of three members: two appointed by the chair of the Mathematical Optimization Society (MOS) and one appointed by the president of the (AMS). Members serve three-year terms, with overlapping appointments to ensure continuity, and may participate in up to two award cycles. The committee chair is initially an appointee of the MOS, with subsequent chairs selected internally by the committee, preferably from among experienced prior members who are senior experts in . The conducts its through correspondence, such as or videoconference, and devises its own procedures for reviewing nominations and identifying potential papers. Nominations, which include the paper reference and a supporting , are submitted directly to the . The assesses submissions based on mathematical quality and significance, with a particular emphasis on ensuring that contributions from young or lesser-known mathematicians are not overlooked. To evaluate technical depth, the may independently seek out additional papers beyond formal nominations. In applying the selection criteria, the committee prioritizes outstanding single papers—rather than series or books—published in recognized, well-refereed journals within the six years preceding the International Symposium on Mathematical Programming (ISMP). The focus is on contributions to , interpreted broadly to include areas such as and , balancing theoretical rigor with broader influence on the field. Up to three prizes may be awarded per cycle, with the $1,500 amount divided among joint authors if applicable; ties are possible, but no award is given if submissions do not meet the high standards. Winners are announced and the prizes presented at the opening ceremony of the triennial ISMP, where citations highlighting the selected papers' contributions are read.

Recipients

1979–1994

The Fulkerson Prize, established to honor outstanding papers in , was first awarded in 1979 for contributions published from 1973 to 1978, recognizing breakthroughs that advanced , complexity, and optimization. In that year, Kenneth Appel and Wolfgang Haken received the prize for their seminal work "Every planar map is four colorable, Part I: Discharging," which provided the first of the four-color theorem, resolving a longstanding by showing that any is four-colorable and marking a milestone in . Also in 1979, Richard M. Karp was awarded for "On the computational complexity of combinatorial problems," which systematically classified numerous decision problems as NP-complete, laying the groundwork for modern in . Paul D. Seymour earned recognition for "The matroids with the max-flow min-cut property," characterizing matroids where the holds, with profound implications for network flows and structural . In 1982, awards highlighted progress in polynomial-time solvability and convex optimization. Leonid G. Khachiyan was honored for "A polynomial algorithm in linear programming," introducing the ellipsoid method that proved linear programming solvable in polynomial time, a pivotal result showing the problem lies in P and inspiring subsequent interior-point methods. Martin Grötschel, László Lovász, and Alexander Schrijver received the prize for "The ellipsoid method and its consequences in combinatorial optimization," demonstrating how the method yields polynomial-time algorithms for problems like separation over rational polyhedra and separation of the stable set polytope, bridging theory and practice in integer programming. Additional 1982 recipients included D.B. Judin and A.S. Nemirovskii for foundational work on the informational complexity of convex problems; G.P. Egorychev and D.I. Falikman independently for solving van der Waerden's conjecture on permanents of doubly stochastic matrices, providing sharp bounds on the permanent function. The 1985 prizes emphasized algorithmic advances in discrepancy theory, , and . József Beck was awarded for "Roth's estimate of the discrepancy of integer sequences is nearly sharp," establishing tight bounds on the discrepancy of arithmetic progressions and influencing . Hendrik W. Lenstra, Jr., received it for "Integer programming with a fixed number of variables," developing a polynomial-time algorithm for fixed-dimension , a key result in geometric and parametric optimization. Eugene M. Luks was recognized for "Isomorphism of graphs of bounded valence can be tested in polynomial time," providing the first polynomial-time algorithm for in bounded-degree graphs using techniques. By 1988, the focus shifted to efficient network algorithms and linear programming innovations. Éva Tardos earned the prize for "A strongly polynomial minimum cost circulation algorithm," yielding the first strongly polynomial-time solution for minimum-cost flows in networks, with broad applications in operations research and transportation. was awarded for "A new -time for ," introducing the that revolutionized practical linear programming solvers and led to widespread commercial adoption. In 1991, recipients advanced volume computation, polyhedral inequalities, and universality in configurations. Martin Dyer, Alan Frieze, and were honored for "A random polynomial time algorithm for approximating the of convex bodies," providing a randomized polynomial-time method for estimation, crucial for sampling and integration in high dimensions. Alfred Lehman received it for "The width-length inequality and degenerate projective planes," establishing inequalities linking polyhedral widths to combinatorial structures in . Nikolai E. Mnev was recognized for "The universality theorems on the classification problem of configuration varieties and convex varieties," proving universality results that connect realizations to topological moduli spaces. The 1994 awards addressed spline homology, polyhedral diameters, and graph colorings. Louis Billera was awarded for "Homology of smooth splines: Generic triangulations and a of Strang," resolving aspects of spline homology through generic triangulations and confirming a on spline spaces. Gil Kalai received it for "Upper bounds for the diameter and height of graphs of the convex polyhedra," providing improved bounds on the of polyhedral graphs, impacting the Hirsch and optimization over polytopes. , Paul D. Seymour, and were honored for "Hadwiger's for K6-free graphs," proving the for graphs without K6 minors, advancing structural and coloring. These early Fulkerson Prizes underscored foundational progress in , optimization algorithms, and polyhedral , establishing benchmarks for computational feasibility and theoretical depth in .

1997–2010

In the years 1997 to 2010, the Fulkerson Prize recognized pioneering contributions that advanced probabilistic , approximation techniques in optimization, structure, submodular minimization, primality testing, approximation of permanents, theory, conjectures, , and smoothed . 1997
Jeong Han Kim received the prize for his paper "The Ramsey Number R(3,t) Has Order of Magnitude t²/log t," published in Random Structures & Algorithms 7 (1995), 173–207. This work established that the Ramsey number R(3,t), which denotes the smallest number of vertices guaranteeing a of size 3 or an independent set of size t in any graph, grows asymptotically as Θ(t² / log t), resolving a 60-year-old problem by tightening the lower bound to match the known upper bound from Ajtai, Komlós, and Szemerédi. The result exemplified the power of probabilistic methods in , influencing subsequent research on Ramsey bounds. 2000
Michel X. Goemans and David P. Williamson were awarded for "Improved approximation algorithms for and problems using ," Journal of the ACM 42 (1995), 1115–1145. Their paper introduced relaxations to achieve a 0.878-approximation ratio for the problem—surpassing previous guarantees—and extended similar techniques to MAX-2SAT and MAX-Ek-SAT, marking a seminal shift toward in combinatorial approximation. Michele Conforti, Gérard Cornuéjols, and M. R. Rao received the prize for " of balanced matrices," Journal of Combinatorial Theory, Series B 77 (1999), 292–406. This contribution provided a polynomial-time for balanced 0-1 matrices into totally unimodular and network matrices, enabling recognition of balanced matrices and advancing polyhedral for applications. 2003
Jim F. Geelen, A. M. H. Gerards, and Ajai Kapoor were honored for "The Excluded Minors for GF(4)-Representable ," Journal of Combinatorial Theory, Series B 79 (2000), 247–299. Their work characterized representable over the GF(4) via a finite set of excluded minors, confirming Rota's conjecture for this case and overcoming challenges in non-unique representations to revitalize matroid theory. Bertrand Guenin earned the prize for "A of weakly bipartite graphs," Journal of Combinatorial Theory, Series B 83 (2001), 112–168. The paper delivered an excluded minor of weakly bipartite graphs, resolving a graphical instance of Seymour's conjecture through an innovative application of Lehman's theorem, with implications for polyhedral relaxations in optimization. Satoru Iwata, Lisa Fleischer, and Satoru Fujishige, along with independent work by Alexander Schrijver, were recognized for their combinatorial algorithms minimizing submodular functions in strongly time: Iwata et al., "A combinatorial, strongly -time algorithm for minimizing submodular functions," Journal of the ACM 48 (2001), 761–777; Schrijver, "A combinatorial minimizing submodular functions in strongly time," Journal of Combinatorial Theory, Series B 80 (2000), 346–355. These developments provided the first combinatorial, strongly -time solutions to submodular minimization—a of —with broad applications in network flows and . 2006
Manindra , Neeraj , and Nitin received the award for "PRIMES is in P," Annals of 160 (2004), 781–793. Their deterministic polynomial-time algorithm for primality testing, based on elliptic curves and modular composition, placed the problem PRIMES in the P, resolving a major open question in since 1976. Mark Jerrum, Alistair Sinclair, and Eric Vigoda were awarded for "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries," Journal of the ACM 51 (2004), 671–697. The paper devised the first fully polynomial randomized approximation scheme (FPRAS) for the permanent using methods and spectral techniques, enabling efficient estimation for nonnegative matrices central to and . Neil Robertson and Paul D. Seymour gained recognition for "Graph Minors. XX. Wagner's conjecture," Journal of Combinatorial Theory, Series B 92 (2004), 325–357. This culmination of their graph minors project proved Wagner's conjecture by showing that every minor-closed family of graphs is characterized by a of forbidden minors, providing a structural foundation for and algorithm design. 2009
Maria Chudnovsky, , Paul Seymour, and were awarded for "The strong perfect graph theorem," Annals of Mathematics 164 (2006), 51–229. Their proof established that a graph is if and only if its complement is Berge (odd-hole- and odd-antihole-free), resolving the 45-year-old strong and unifying key concepts in and optimization. Thomas C. Hales and Samuel P. Ferguson shared the prize for proving the : Hales, "A proof of the Kepler conjecture," Annals of Mathematics 162 (2005), 1065–1185; Ferguson, "Sphere Packings, V. Pentahedral Prisms," Discrete & Computational Geometry 36 (2006), 167–204. Using , , and exhaustive computer case analysis, they confirmed that the densest packing of equal spheres in three dimensions achieves π/(3√2) density, settling a problem posed by Kepler in 1611. Daniel A. Spielman and Shang-Hua Teng received the award for "Smoothed : Why the simplex algorithm usually takes polynomial time," Journal of the ACM 51 (2004), 385–463. They introduced smoothed analysis, demonstrating that the simplex method for runs in expected polynomial time under Gaussian perturbations of inputs, bridging worst-case and average-case complexity for practical algorithms. These awards underscored the prize's role in fostering interdisciplinary progress, from theoretical barriers to computational tools, during a era of rapid growth in discrete algorithms.

2012

In 2012, the Fulkerson Prize recognized outstanding contributions in graph partitioning approximations, random graph factors, and limits of dense graphs, presented at the International Symposium on Mathematical Programming. 2012
Sanjeev Arora, Satish Rao, and were awarded for "Expander flows, geometric embeddings and graph partitioning," Journal of the ACM 56 (2009), 1–37. Their paper introduced expander flows to improve the approximation ratio for graph separators and partitioning problems, with applications to network design and . Anders Johansson, Jeff Kahn, and Van H. Vu received the prize for "Factors in random graphs," Random Structures & Algorithms 33 (2008), 1–28. The work determined the threshold probability for the existence of factors (H-factors) in random graphs, resolving a central question in probabilistic via the second moment method. László Lovász and Balázs Szegedy were honored for "Limits of dense graph sequences," Journal of Combinatorial Theory, Series B 96 (2006), 933–957. This foundational paper developed the theory of graphons as limits of dense graph sequences, providing a framework for analyzing subgraph densities and convergence properties in .

2014–2024

The Fulkerson Prize continued to recognize groundbreaking contributions in during this period, with awards presented in 2015, 2018, 2021, and 2024, reflecting the prize's triennial cycle. These selections highlight advances in polyhedral theory, , computational complexity, algorithmic graph theory, convex body algorithms, high-dimensional geometry, and Boolean function analysis.
YearRecipientsContribution
2015Francisco SantosFor constructing a counterexample to the Hirsch conjecture, which posited that the diameter (graph distance between vertices) of a d-dimensional polytope with n facets is at most n − d; Santos built a 43-dimensional polytope with 86 facets having diameter at least 44, disproving the conjecture and combining techniques from polyhedral combinatorics and geometric methods.
2018Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, Robert MorrisFor determining the precise threshold probabilities in random graphs beyond which every graph is H-colorable for any fixed graph H, resolving long-standing questions in extremal graph theory and Ramsey-type problems on chromatic thresholds.
2018Thomas RothvoßFor proving that the perfect matching polytope in the complete graph on n vertices has exponential extension complexity (at least 2Ω(n)2^{\Omega(\sqrt{n})}
2021Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, Andrew TreglownFor proving the 1-factorization conjecture and Hamilton decomposition conjecture of Baranyai and Nash-Williams from the 1970s–1980s, using a unified approach based on graph replacement methods to decompose regular tournaments and hypergraphs into perfect matchings.
2021Jin-Yi Cai, Xi ChenFor resolving the complexity dichotomy for counting constraint satisfaction problems (CSPs) with complex weights, showing that such partition functions are either polynomial-time computable or #P-hard, with applications to approximate counting, sampling, and statistical physics models.
2021Ken-ichi Kawarabayashi, Mikkel ThorupFor developing a deterministic algorithm to compute edge connectivity in undirected graphs in near-linear time (O(m log n)) time, introducing novel techniques like fast deterministic graph sparsification and expander decomposition.
2024Ben Cousins, Santosh VempalaFor introducing Gaussian cooling, a Markov chain method yielding the fastest O*(n3) algorithms for approximating the volume of convex bodies and sampling from Gaussian distributions over them, advancing randomized algorithms in high dimensions with ties to machine learning.
2024Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, Yufei ZhaoFor solving the maximum equiangular lines problem by proving that the maximum number of equiangular lines in ℝd with fixed angle θ is at most roughly d3/2 for large d, using spectral graph theory and linear algebra bounds.
2024Nathan Keller, Noam LifshitzFor extending the junta method from Boolean functions to hypergraphs, resolving the Erdős–Chvátal simplex conjecture on the maximum size of intersection-free families and advancing Turán-type problems in extremal set theory.
Recent awards underscore evolving trends in , including the integration of probabilistic and algorithmic tools with applications (as in volume computation), explorations in high-dimensional and methods, and analytic approaches to Boolean analysis and extremal problems. No award has been given in 2025, with the next expected in 2027 per the triennial schedule.
Add your contribution
Related Hubs
User Avatar
No comments yet.