Home | Contact | About MOS | Membership | Publications | Prizes | Meetings | IPCO | ISMP | Links | Album | Jobs
Mathematical Optimization Society

MOS Prizes

MOS Prizes


2015 Fulkerson Prize Citation

Francisco Santos,
"A Counterexample to the Hirsch Conjecture", Annals of Mathematics, 2012

The Hirsch conjecture states that in any d-dimensional polytope with n facets, the edge distance between any pair of vertices (the diameter of the skeleton graph) is bounded from above by n - d. As stated, the conjecture provides a simple and elegant bound on the worst-case behavior of a primal simplex algorithm in terms of the number of nondegenerate pivots, provided a clairvoyant pivot strategy is used.

For almost 50 years, many well-known mathematicians have tried unsuccessfully to settle the conjecture, until a counterexample was cleverly constructed by Francisco Santos.

Santos constructs a 43-dimensional polytope with 86 facets having diameter at least 44. So it lives in a space where intuition has left most of us.

To construct the counterexample, Santos combines ideas and techniques stemming from various disciplines of mathematics. Although he gives a negative answer to a highly visible and more than half a century old conjecture, his methods substantially influence today's mathematics. This is witnessed by the large number of follow-up papers that build on this award-winning paper and carry his techniques further on.