The Hirsch conjecture holds for normal flag complexes

Introduction

A natural problem in linear programming is the question how many iteration steps of the simplex method are required in order to solve a linear optimization problem in $d$ variables and given by $n$ linear inequalities. In other words, given an arbitrary polyhedron of dimension $d$ and with $n$ facets, how far away can two vertices possibly be? The distance between vertices is here measured by counting the number of edges one has to walk along, in order to move from one vertex to the other.

An elegant answer was proposed in the Sixties by Warren Hirsch in a letter to George Dantzig:

Let $Q$ denote a $(d+1)$-dimensional polyhedron with $n$ facets. Then the diameter of the $1$-skeleton of $Q$ is $\leq n-(d+1)$.

The case of unbounded polyhedra was quickly resolved when a counterexample was given by Klee and Walkup [KW67]. It remained to treat the case of bounded polyhedra (that is, polytopes), the bounded Hirsch conjecture. We state the conjecture in a form dual to the classical formulation.

The diameter of the facet-ridge graph of any $(d+1)$-polytope on $n$ vertices is $\leq n-(d+1)$.

An equivalent conjecture, the $W_{v}$-conjecture, or non-revisiting path conjecture, was introduced in the Sixties by Klee and Wolfe, cf. [Kle65].

For any two facets of a simplicial polytope $R$ there exists a non-revisiting path connecting them.

Conversely, Klee and Kleinschmidt [KK87] showed that if there is a polytope $R$ which violates the $W_{v}$-conjecture, then from $R$ one can construct a (possibly different) polytope $P$ that violates the Hirsch conjecture.

Conjectures 1.2 and 1.3 have been disproved recently by Santos [San12]. So the bound $n-(d+1)$ for the diameter is not correct. Little do we know about how the correct bound should look like. At the moment, we do not know whether a linear or even a polynomial upper bound exist. Some of the best upper bounds known so far are the bounds $2^{d-1}n$ by Larman [Lar70] (compare also [Bar74]), and the bound $n^{\log(d+1)+1}$ by Kalai [Kal92, KK92]. These bounds apply more generally to the class of normal $d$-complexes, i.e., complexes where all links of faces of codimension $\geq 2$ are connected. (This is a common setting for the study of abstractions of the Hirsch conjecture, compare also Eisenbrand et al [EHRR10].)

In this paper, we confirm the validity of the Hirsch conjecture for flag polytopes and more generally flag and normal complexes. All polytope boundaries, all spheres, all triangulated manifolds, and even all Cohen–Macaulay complexes are normal.

Let $C$ be any flag normal $d$-complex with $n$ vertices. Between any two facets of $C$ there is a non-revisiting path. Hence, the dual graph of $C$ has diameter $\leq n-(d+1)$.

We provide two proofs of Theorem 1.4: a geometric proof (Section 2), which follows from a result by Gromov on spaces of curvature bounded above, and a combinatorial proof (Section 3), which is more elementary, but also less intuitive.

Let $C$ be any flag simplicial complex. When we endow $C$ with the right-angled metric, the star of every vertex of $C$ is geodesically convex.

Say we have a flag normal complex and we want to find a non-revisiting path. Our idea is to endow it with the right-angled metric, and then ‘follow’ the segments, that is, the shortest geodesics inside the metric space. In fact, the intersection of any segment with an open convex set is obviously a segment (or the empty set). In particular, any segment intersects the interior of any vertex star in a connected set (possibly empty). In other words, no segment revisits a vertex star it has previously left. If we approximate a segment $\gamma$ with the dual path formed by the $d$-faces crossed by $\gamma$, the path we obtain is non-revisiting and we are done.

While the ‘flag’ assumption is needed for the convexity of vertex stars, one might wonder whether the ‘normal’ assumption is at all needed in the argument above. The truth is that we have hidden a minor technical difficulty under the carpet. Namely, a segment might go from a $d$-face $X$ to a $d$-face $Y$ by passing through a face $\sigma$ of dimension $\leq d-2$. Even if they share a vertex, $X$ and $Y$ are not (necessarily) adjacent in the dual graph; so if $C$ is not normal, it is not clear how to find a non-revisiting dual path from $X$ to $Y$ inside the star of $\sigma$. The natural way to “bridge” between $X$ and $Y$, is to consider the link of $\sigma$ and use induction. For this we need $C$ to be normal.

Theorem 1.4 has several interesting consequences. Recall that a simplicial complex is a triangulated manifold if the union of its faces, as topological space, is homeomorphic to a manifold.

All flag triangulations of connected manifolds satisfy the non-revisiting path property, and in particular the Hirsch diameter bound.

Recall that a simplicial polytope is flag if its boundary complex is a flag complex. Corollary 1.5 specializes to this class as follows:

Every flag polytope satisfies the non-revisiting path property, and in particular the Hirsch diameter bound.

By a result of Provan and Billera [PB80], every vertex-decomposable simplicial complex satisfies the Hirsch diameter bound. As a corollary, they obtain the following famous result:

Let $C$ be any shellable simplicial $d$-complex. Then the derived subdivision $\operatorname{sd}C$ of $C$ satisfies the Hirsch diameter bound. In particular, if $C$ is the boundary complex of any polytope, then $\operatorname{sd}C$ satisfies the Hirsch diameter bound.

The derived subdivision of an arbitrary triangulated manifold, however, is not vertex-decomposable in general. The reasons are two: There are topological obstructions (all vertex-decomposable manifolds are spheres or balls) as well as combinatorial obstructions (some spheres have non-vertex-decomposable derived subdivisions, cf. [HZ00, BZ11]). That said, the derived subdivision of any simplicial complex is flag. So, by Corollary 1.5, we have the following:

The derived subdivision of any triangulation of any connected manifold satisfies the Hirsch diameter bound.

2 Set-up

Recall that an (abstract) simplicial complex is pure if all its inclusion-maximal faces (the facets) have the same dimension. If $C$ is an abstract simplicial complex on $n$ vertices, any subset of $\{1,\ldots,n\}$ not in $C$ is a non-face.

A simplicial complex $C$ is flag if every inclusion minimal non-face is a $2$-element set (that is, an edge).

If $C$ is a pure simplicial $d$-complex on $n$ vertices, the dual graph or facet-ridge graph of $C$, denoted by $G^{\ast}(C)$, is constructed as follows. The set of vertices of $G^{\ast}(C)$ consists of the facets of $C$; we connect two vertices by an edge if the corresponding facets have a $(d-1)$-face in common. We define $\operatorname{diam}(C)$ as the diameter of the graph $G^{\ast}(C)$. We say that $C$ satisfies the Hirsch diameter bound if $\operatorname{diam}(C)\leq n-(d+1).$

We shall therefore identify elements of link and combinatorial link.

All curves and paths are considered with their natural order from the startpoint (the image of $\min I$) to the endpoint (the image of $\max I$). For example, the last facet of a facet path $\Gamma$ in a subcomplex $S$ of $C$ is the image of the maximal $z\in I$ such that $\gamma(z)\in S$. As common in the literature, we will not strictly differentiate between a curve (or path) and its image; for instance, we will write $\gamma\subset S$ to denote the fact that the image of a curve $\gamma$ lies in a set $S$.

If $\gamma$ and $\delta$ are two curves in any metric space such that the endpoint of $\gamma$ coincides with the starting point of $\delta$, we use the notation $\gamma\cdot\delta$ to denote their concatenation or product (cf. [BBI01, Sec. 2.1.1.]). Analogously, if the last facet of a facet path $\Gamma$ and the first facet of a facet path $\Delta$ coincide, we can concatenate $\Gamma$ and $\Delta$ to form a facet path $\Gamma\cdot\varDelta$. Concatenations of more than two paths are represented using the symbol $\prod$.

Any pure simplicial complex that satisfies the $W_{v}$-property satisfies the Hirsch diameter bound.

The geometric proof

In this section, we give a geometric proof of Theorem 1.4. We need some modest background from the theory of spaces of curvature bounded above, which we review here. For a more detailed introduction, we refer the reader to the textbook by Burago–Burago–Ivanov [BBI01].

Right-angled simplices and convex vertex-stars

For us, a geometric (spherical) simplex of dimension $d$, or geometric d-simplex, is the convex hull of $d+1$ points in general position in $S^{d}$. A geometric simplex $\Delta$ is right-angled if all dihedral angles of $\Delta$ are equal to $\nicefrac{{\pi}}{{2}}$. Equivalently, $\Delta$ is right-angled if it is regular and of diameter $\nicefrac{{\pi}}{{2}}$. By convention, every -simplex is right-angled as well.

With this notion, Proposition 2.1 gives the following:

Geometric proof of Theorem 1.4.

The proof, as well as the construction of the desired facet path, is by induction on the dimension $d$ of $C$. The case $d=0$ is easy: If $X$ consists of an element of $\mathcal{Y}$, the path is trivial of length . If not, the desired facet path is given by $\Gamma:\{0,1\}\mapsto C$, with $\Gamma(0):=X$ and $\Gamma(1):=Y$, where $Y$ is any facet of $C$ consisting of an element of $\mathcal{Y}$. We proceed by induction on $d$, assuming that $d\geq 1$.

for any collection $\mathcal{\varOmega}$ of points in $C$. Clearly, $\operatorname{T}_{\alpha}^{\mathcal{\varOmega}}$ is finite.

Returning to the proof, let $x_{0}$ denote any point of $X_{0}:=X$ minimizing the distance to the set $\mathcal{Y}_{0}:=\mathcal{Y}$. Set $i:=0$. The construction process for the desired facet path goes as follows:

Now, increase $i$ by one, and repeat the construction procedure from the start.

To prove the claim, we need only apply an easy induction on the dimension:

If $i=j$: By induction assumption, the facet path $\Gamma^{\prime}_{X^{\prime}_{i}X^{\prime}_{i+1}}$ (as defined above) is non-revisiting. Thus, the facet path $\Gamma_{[\chi_{i},\chi_{i+1}]}$, which coincides with $\Gamma_{X_{i}X_{i+1}}=\sigma_{i}\ast\Gamma^{\prime}_{X^{\prime}_{i}X^{\prime}_{i+1}}$ up to reparametrization, is non-revisiting. Since $\Gamma_{[a,b]}$ is a subpath of $\Gamma_{[\chi_{i},\chi_{i+1}]}$, this finishes the proof of this case.

If $X$ and $Y$ are any two facets of $C$, apply Lemma 2.3 to the facet $X$ and the set $\mathcal{Y}=\{y\}$, where $y$ is any interior point of $Y$. ∎

We can give the first proof of Theorem 1.4.

The combinatorial proof

In this section, we give a purely combinatorial proof of Theorem 1.4. The proof is articulated into two parts: First we construct a facet path between any pair of facets of $C$, the so called combinatorial segment, and then we prove that the constructed path satisfies the non-revisiting path property.

Part 1: From any facet $X$ to any vertex set $\mathcal{Y}$.

We construct a facet path from a facet $X$ of $C$ to a subset $\mathcal{Y}$ of $\operatorname{F}_{0}(C)$, i.e. a facet path from $X$ to a facet intersecting $\mathcal{Y}$, with the property that $\mathcal{Y}$ is intersected by the path $\Gamma$ only in the last facet of the path.

If $C$ is -dimensional, and $X$ consists of an element of $\mathcal{Y}$, the path is trivial of length . Else, the desired facet path is given by $\Gamma:\{0,1\}\mapsto C$, where $\Gamma(0):=X$ and $\Gamma(1):=Y$, which is any facet consisting of an element of $\mathcal{Y}$ .

The concatenation of these facet paths is a combinatorial segment from $X$ to $\mathcal{Y}$.

Part 2: From any facet $X$ to any other facet $Y$.

The combinatorial segment is non-revisiting

We start off with some simple observations and notions for combinatorial segments in complexes of dimension $d\geq 1$.

Indeed, if on the other hand $j-i=2$, then $v$, seen as an element in the combinatorial link of $x_{i}$ in $C$, is a vertex in $\operatorname{T}_{x_{i}}^{\mathcal{Y}_{i}}$. Therefore, either $v$ or another vertex of $\Gamma(a)$ coincides with the pearl $x_{i+1}$, which contradicts the assumption that $x_{i}\neq x_{i+1}$ is the pearl associated to $a$.

References