Tuesday, 13:15 - 13:40 h, Room: H 3008


Francisco Santos
Counter-examples to the Hirsch conjecture


About two years ago I announced the first counter-example to
the (bounded) Hirsch conjecture: a 43-dimensional polytope
with 86 facets and diameter (at least) 44. It was based on
the construction of a 5-prismatoid of "width'' 6, with 48
vertices. Since then, some improvements or related results
have been obtained: S.-Stephen-Thomas showed that prismatoids
of dimension 4 cannot lead to non-Hirsch polytopes, and
S.-Matschke-Weibel constructed smaller 5-prismatoids of
length 6, now with only 25 facets. These produce
counter-examples to the Hirsch conjecture in dimension 20.
But, all in all, the main problem underlying the Hirsch
Conjecture remains as open as before. In particular, it would
be very interesting to know the answer to any of the following

  1. Is there a polynomial bound f(n) for the diameter of
    n-faceted polytopes? ("Polynomial Hirsch Conjecture'').
  2. Is there a linear bound? Is f(n)=2n such a bound?

A conjecture of Hänle, suggested by the work of Eisenbrand et
al. in the abstract setting of "connected layer sequences''
would imply that nd is an upper bound.


Talk 1 of the invited session Tue.2.H 3008
"Combinatorics and geometry of linear optimization I" [...]
Cluster 2
"Combinatorial optimization" [...]


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. All this happens in case of bad medicines and wrong way of medication. Viagra Super Force is a treatment that has unique and surpassing formula combination.