Given a d-dimensional convex polytope with n facets, how many edges do
we have to walk on, to go from one vertex to another? In 1957 Hirsch
conjectured that n-d yields a universal upper bound for such distance.
The conjecture was disproved in 2010 by Santos.

So the bound n-d is wrong; but we don't know much of what the correct
guess should be. The question has a natural interpretation in
optimization, namely, we are asking if the simplex method has linear
running time (in the worst case scenario).

On the plus side, Lou Billera and Scott Provan discovered in the
Seventies that given an arbitrary polytope, its barycentric
subdivision does satisfy the Hirsch conjecture. The proof uses
shellability, a nice combinatorial property that all polytope
boundaries have.

We present a new explanation of this result (joint with Karim
Adiprasito): Indeed, every flag polytope satisfies the Hirsch
conjecture. (And also flag homology manifolds - so neither
shellability, nor the topology play a role in our proof.) The proof
uses a metric criterion by Gromov, which I will briefly explain.