## Invited Session Tue.2.H 3008

#### Tuesday, 13:15 - 14:45 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Combinatorics and geometry of linear optimization I

**Chair: Antoine Deza and Jesus Antonio De Loera**

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

**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.

**Tuesday, 13:45 - 14:10 h, Room: H 3008, Talk 2**

**Nicolai Hähnle**

An abstract view on the polynomial Hirsch conjecture

**Abstract:**

The question of whether a strongly polynomial algorithm for linear programming exists is one of the great mysteries of the field. It has motivated the polynomial Hirsch conjecture, which claims that the diameter of the vertex-edge graph of every polyhedron is bounded by a polynomial in its affine dimension and the number of facets.

The best known upper-bound on the diameter of polyhedra is a quasi-polynomial bound due to Kalai and Kleitman. What properties of polyhedra make this upper bound work? What techniques could be useful in improving it? We present a purely combinatorial abstraction of the graph of a polyhedron as a way of understanding these questions better. In particular, we present an abstraction in which an almost quadratic construction is known, while the Kalai-Kleitman bound still holds with essentially the same proof.

We made the conjecture that an upper bound of *d(n-1)* holds for this abstraction. We present some evidence for and against this conjecture, and discuss open questions that could guide possible approaches to the polynomial Hirsch conjecture.

**Tuesday, 14:15 - 14:40 h, Room: H 3008, Talk 3**

**Yuriy Zinchenko**

Polytopes and arrangements: Diameter and curvature

**Coauthors: Antoine dDeza, Tamas Terlaky**

**Abstract:**

We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature, and a continuous analogue of a d-step equivalence result for the diameter of a polytope. Potential extensions of this work will be highlighted.