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

**Francisco Santos**

Counter-examples to the Hirsch conjecture

**Abstract:**

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

questions:

- Is there a polynomial bound
*f(n)* for the diameter of

*n*-faceted polytopes? ("Polynomial Hirsch Conjecture'').

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