Personal tools
You are here: Home Events Lab Lunch by Mary Cryan

Lab Lunch by Mary Cryan

— filed under:

the Hirsch conjecture

What
  • Lab Lunch
When Mar 17, 2015
from 01:00 PM to 02:00 PM
Add event to calendar vCal
iCal

This will be a survey talk. The Hirsch conjecture,
formulated by Edward A. Hirsch in 1957, proposed an upper bound
for the diameter of the edge-vertex graph of any polytope in
regard to the dimension d, and number of bounding planes n, of
the polytope:  his conjectured upper bound on diameter was (n-d).
Over the years that followed, there was little progress ... The
conjecture was proven for d <= 4; however, for the general case
on polytopes, the best upper bound is not even polynomially-bounded.
In 2010, Francisco Santos disproved the Hirsch conjecture by
constructing a counterexample of dimension 43, with 86 bounding
hyperplanes.

Document Actions