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" [...]


  Online lending company provides a wide range of ways to get money by means of Tennessee Loans Online. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Order Levitra, but also as part of its analogs.