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.