2015 Fulkerson Prize Citation
"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.