2009 Fulkerson Prize Citation
Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas
"The strong perfect graph theorem", Annals of Mathematics 164 (2006) 51-229.
Claude Berge introduced the class of perfect graphs in 1960 together with a possible
characterization in terms of forbidden subgraphs. The resolution of Berge's strong perfect
graph conjecture quickly became one of the most sought after goals in graph theory. The
pursuit of the conjecture brought together four important elements: vertex colorings,
stable sets, cliques, and clique covers. Moreover, D. R. Fulkerson established connections
between perfect graphs and integer programming through his theory of anti-blocking
polyhedra. A graph is called perfect if for every induced subgraph H the clique-covering
number of H is equal to the cardinality of its largest stable set. The strong perfect graph
conjecture states that a graph is perfect if and only if neither it nor its complement
contains as an induced subgraph an odd circuit having at least five edges. The elegance
and simplicity of this possible characterization led to a great body of work in the
literature, culminating in the Chudnovsky et al. proof, announced in May 2002, just
one month before Berge passed away. The long, difficult, and creative proof by Chudnovsky
et al. is one of the great achievements in discrete mathematics.
Thomas C. Hales,
"A proof of the Kepler conjecture", Annals of Mathematics 162 (2005) 1063-1183.
Samuel P. Ferguson
"Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36 (2006) 167-204.
In 1611 Johannes Kepler asserted that the densest packing of equal-radius spheres is
obtained by the familiar cannonball arrangement. This statement is known as the Kepler
conjecture and it is a component of Hilbert's 18th problem. After four centuries, Ferguson
and Hales have now proven Kepler's assertion. The Ferguson-Hales proof develops deep
connections between sphere packings and mathematical programming, making heavy use of
linear programming duality and branch and bound to establish results on the density of
candidate configurations of spheres. The beautiful geometric arguments and innovative use
of computational tools make this a landmark result in both geometry and discrete
Daniel A. Spielman and Shang-Hua Teng
"Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time",
Journal of the ACM 51 (2004) 385-463.
George Dantzig's simplex algorithm for linear programming is a fundamental tool in applied
mathematics. The work of Spielman and Teng is an important step towards providing a
theoretical understanding of the algorithm's great success in practice despite its known
exponential worst-case behavior. The smoothed analysis introduced by the authors fits
nicely between overly pessimistic worst-case results and the average-case theory developed
in the 1980s. In smoothed analysis, the performance of an algorithm is measured under small
perturbations of arbitrary real inputs. The Spielman-Teng proof that the simplex algorithm
runs in polynomial-time under this measure combines beautiful technical results that
intersect multiple areas of discrete mathematics. Moreover, the general smoothed analysis
framework is one that can be applied in many algorithmic settings and it is now established
as an important technique in theoretical computer science.