Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture (A combinatorial proof of the Adiprasito-Benedetti theorem.)

This post is authored by Karim Adiprasito

The past months have seen some exciting progress on diameter bounds for polytopes and polytopal complexes, both in the negative and in the positive direction.  Jesus de Loera and Steve Klee described simplicial polytopes which are not  weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about  was proved  by Hähnle, Klee, and Pilaud in the paper  Obstructions to weak decomposability for simplicial polytopes. In this post I want to outline a generalization of a beautiful result of Billera and Provan in support of the Hirsch conjecture.

I will consider the simplicial version of the Hirsch conjecture, dual to the classic formulation of Hirsch conjecture. Furthermore, I will consider the Hirsch conjecture, and the non-revisiting path conjecture, for general simplicial complexes, as opposed to the classical formulation for polytopes.

Theorem [Billera & Provan `79] The barycentric subdivision of a shellable simplicial complex satisfies the Hirsch Conjecture.

The barycentric subdivision of a shellable complex is vertex decomposable. The Hirsch diameter bound for vertex decomposable complexes, in turn, can be proven easily by induction.

This is particularly interesting since polytopes, the objects for which the Hirsch conjecture was originally formulated, are shellable. So while in general polytopes do not satisfy the Hirsch conjecture, their barycentric subdivisions always do! That was a great news!

Shellability is a strong combinatorial property that enables us to decompose a complex nicely, so it does not come as a surprise that it can be used to give some diameter bounds on complexes. Suprisingly, however, shellability is not needed at all!  And neither is the barycentric subdivision!

A simplicial complex Σ is called flag if it is the clique complex of its 1-skeleton. It is called normal if it is pure and for every face F of Σ of codimension two or more, Lk(F,Σ) is connected.

Theorem (Adiprasito and Benedetti):  Any flag and normal simplicial complex Σ satisfies the non-revisiting path conjecture and, in particular, it satisfies the Hirsch conjecture.

This generalizes the Billera–Provan result in three ways:

— The barycentric subdivision of a simplicial complex is flag, but not all flag complexes are obtained by barycentric subdivisions.

— Shellability imposes strong topological and combinatorial restrictions on a complex; A shellable complex is always homotopy equivalent to a wedge of spheres of the same dimension, and even if a pure complex is topologically nice (if, for example, it is a PL ball) it may not be shellable, as classic examples of Goodrick, Lickorish and Rudin show. Being normal still poses a restriction, but include a far wider class of complexes. For example, every triangulation of a (connected) manifold is normal, and so are all homology manifolds.

— Instead of proving the Hirsch conjecture, we can actually obtain the stronger conclusion that the complex satisfies the non-revisiting path conjecture, which for a given complex is stronger than the Hirsch conjecture.

A geometric proof of our theorem appeared in a recent paper “Metric geometry and collapsibility”  with Bruno Benedetti. . I will give here a short combinatorial proof.

Construction of a combinatorial segment

Preliminaries

Lk(F,Σ) shall denote the link of a face F of Σ, and St(F,Σ) shall denote the star of F in Σ. Let denote the distance between two vertices in the 1-skeleton of Σ. Let denote the distance between two vertex sets S, T in Σ. Let denote the pairs of points in S, T that realize the distance , and let resp. denote the set of vertices of T realizing the distance resp. the set of points y in Lk(x,Σ) with the property that . A vertex path shall mean a path in the 1-skeleton of Σ, and facet path is short for facet-ridge path.

Part 1: From a facet X to a vertex set S.

We construct a facet path from a facet X of Σ to a subset S of the vertex set of Σ, i.e. a facet path from X to a facet intersecting S, with the property that S is intersected by the path Γ only in the last facet of the path.

If Σ is 1-dimensional, choose a shortest vertex path realizing the distance . The edges in that path, including X, give the desired facet path.

If Σ is of a dimension d larger than 1, set , and proceed as follows:

1. If intersects S, stop the algorithm. If not, proceed to step 2.

2. Let be any vertex of that minimizes the distance to S. Set . Using the construction for dimension d-1, we can construct a facet path in  from the facet to the vertex set . By considering the join of the elements of that path with , we obtain a facet path from to the vertex set . Call the last facet of the path , and the vertex of it intersects .

Repeat the procedure with instead of , instead of , and instead of . The process stops once the facet path constructed intersects S.

Part 2: From a facet X to another facet Y.

Using Part 1., construct a facet path from X to a vertex z of the vertex set of Y, and let Z denote the last facet of the path.

If Σ is of dimension 1, complete the path to a facet path from X to Y by adding the facet Y to the path.

If Σ is of dimension d greater than 1, apply the (d-1)-dimensional construction to construct a facet path in Lk(z,Σ) from Lk(z,Z) to Lk(z,Y), and lift this to a facet path in Σ by joining the elements of the path with .

This finishes the construction. We call the facet paths constructed combinatorial segments.

The combinatorial segment is non-revisiting.

We start off with some simple observations and notions for combinatorial segments:

1. A combinatorial segment Γ comes with a path (see Part 1. of the construction). This is a shortest path in the 1-skeleton, realizing the distance , called the thread t of the combinatorial segment Γ.

2. Every facet of the combinatorial segment Γ is associated to a vertex of the thread like this: F intersects the thread t, and there is a unique i such that F contains in t, but not . Call  the pearl of F in t.

We consider a combinatorial segment and its thread with the natural order from X to S resp. from X to Y.

Lemma S: If F is a facet of Γ, where F has pearl $latex x_i$ in t, and v is a vertex of Γ s.t. F and lie in St(v,Σ), then the first facet G of Γ whose pearl is is a facet of St(v,Σ) as well, and the part of the combinatorial segment from F to G lies in St(v,Σ).

Proof: The lemma is clear if v is in t (i.e. v coincides with or ). To see the case v not in t, we can use induction on the dimension of Σ:

For 1-dimensional complexes, this is again clear.

If Σ is of dimension d larger than 1, consider the (d-1)-complex . is a facet of the combinatorial segment . Since the complex contains and since Σ is flag, we obtain that St(v,Σ’) contains . Furthermore, F’ is clearly contained in St(v,Σ’). Thus, by induction assumption, the portion of from F’ to the first facet G’ of Γ’ containing is contained in St(v,Σ’). Since the combinatorial segment in the relevant part from to is obtained from  by join with (i.e. ), we have the desired statement. This finishes the proof of the Lemma.

This suffices to prove that a combinatorial segment Γ must be non-revisiting:

Proof of the Theorem: Consider a combinatorial segment Γ that connects a facet X with a facet Y of Σ. Let A, B be any two facets of Γ, with pearls in t respectively that both lie in the star of a vertex of v in Σ. Then the part of Γ from A to B (B coming, w.l.o.g., after A in Γ) lies in the star St(v,Σ) of v entirely.To see this, there are two cases to consider:

If i=j This case follows directly from Lemma S, since B is somewhere between A and the first facet G of Γ to be associated with , so , as desired.

If i<j In this case, we have i+1=j. Now, St(v,Σ) includes since it includes B, and if C is the first facet of Γ associated to , then lies in St(v,Σ) by Lemma S, and, since lies in St(v,Σ) by the argumentation for i=j, we have that , as desired.

Thus, for and , we have , finishing the proof that Γ is non-revisiting.