2015 Fulkerson Prize Citation
Francisco Santos,
"A Counterexample to the Hirsch Conjecture", Annals of Mathematics, 2012
The Hirsch conjecture states that in any ddimensional 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
worstcase 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 wellknown mathematicians have tried unsuccessfully to settle the
conjecture, until a counterexample was cleverly constructed by Francisco Santos.
Santos constructs a 43dimensional 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 followup papers that build on this
awardwinning paper and carry his techniques further on.
