Graphs of polytopes form an important part of polytope theory, since the graph encodes a lot about the combinatorial structure of the polytope. In particular, bounding the diameter of the graph of a polytope is a well-known and long-standing open problem. A great theoretical and practical interest in this question originates from the desire to efficiently solve Linear Programming, since the existence of a polynomial (in the number of polytope facets) bound on the diameter is a necessary condition for the yet undecided existence of a polynomial time variant of the Simplex-Algorithm.

However, in order to efficiently optimize linear functions over a polytope P, it suffices to efficiently optimize linear functions over an extension Q of P. The latter observation leads to the following question we call Extended Hirsch-Conjecture: Is there a polynomial function q(·) such that every simple polytope P with n facets admits a simple extension Q with at most q(n) facets and diameter at most q(n)?.

This project aims at investigating the above formulated Extended Hirsch-Conjecture, with the goal of collecting results that provide a better understanding of whether allowing for extensions indeed helps in proving small bounds on diameters or whether that problem appears not to be relaxed significantly by this approach.