Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture

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 \sqrt{d} 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


Lk(F) shall denote the link of a face F of Σ, and St(F) shall denote the star of F in Σ. Let d_\Sigma(x,y) denote the distance between two vertices in the 1-skeleton of Σ. Let d_\Sigma(S,T) denote the distance between two vertex sets S, T in Σ. Let p_\Sigma(S,T) denote the pairs of points in Sthat realize the distance d_\Sigma(S,T), and let p_\Sigma(x,T) resp. g_\Sigma(x,T) denote the set of vertices of T realizing the distance d_\Sigma({x},T) resp. the set of points y in Lk(x) with the property that d_\Sigma(\{y\},T)+1=d_\Sigma(\{x\},T). 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 d_\Sigma(X,S). The edges in that path, including X, give the desired facet path.

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

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

2. Let x_0 be any vertex of X_0 that minimizes the distance to S. Set S_0=p_\Sigma({x_0},S). Using the construction for dimension d-1, we can construct a facet path in \mathrm{Lk}(x_0,\Sigma) from the facet \mathrm{Lk}(x_0,X_0) to the vertex set g_\Sigma(x_0,S_0). By considering the join of the elements of that path with x_0, we obtain a facet path from X_0 to the vertex set g_\Sigma(x_0,S_0). Call the last facet of the path X_1, and the vertex of g_\Sigma(x_0,S_0) it intersects x_1.

Repeat the procedure with x_{i+1} instead of x_i, X_{i+1} instead of X_i, and S_{i+1}=d_\Sigma({x_{i+1}},S) instead of S_i. 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 x_0.

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 (x_0, x_1, \dots , x_m) (see Part 1. of the construction). This is a shortest path in the 1-skeleton, realizing the distance m = d_\Sigma(X,S), 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 x_i in t, but not x_{i+1}. Call x_i  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 x_{i+1} lie in St(v,Σ), then the first facet G of Γ whose pearl is x_{i+1} is a facet of St(v,Σ) as well, and the part \Gamma_{FG} 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 x_i or x_{i-1}). 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 \Sigma'=\mathrm{Lk}(x_i,\Sigma). F'=\mathrm{Lk}(x_i,F) is a facet of the combinatorial segment \Gamma' =\mathrm{Lk} (x_i,\Gamma) . Since the complex \mathrm{St}(v,\Sigma) contains x_{i+1} and since Σ is flag, we obtain that St(v,Σ’) contains x_{i+1}. Furthermore, F’ is clearly contained in St(v,Σ’). Thus, by induction assumption, the portion \Gamma'_{F'G'} of \Gamma'=\mathrm{Lk}(x_i,\Gamma) from F’ to the first facet G’ of Γ’ containing x_{i+1} is contained in St(v,Σ’). Since the combinatorial segment \Gamma_{FG} in the relevant part from F=x_i\ast F' to G=x_i\ast G' is obtained from \Gamma'_{FG} by join with x_i (i.e. \Gamma_{FG}=x_i\ast \Gamma'_{FG}), 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 x_i,\, x_j in t respectively that both lie in the star of a vertex of v in Σ. Then the part \Gamma_{AB} 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 x_{i+1}, so \Gamma_{AB}\subset\Gamma_{AG}\subset \mathrm{St}(v,\Sigma), as desired.

If i<j In this case, we have i+1=j. Now, St(v,Σ) includes x_j=x_{i+1} since it includes B, and if C is the first facet of Γ associated to x_{i+1}, then \Gamma_{AC} lies in St(v,Σ) by Lemma S, and, since \Gamma_{CB} lies in St(v,Σ) by the argumentation for i=j, we have that \Gamma_{AB}=\Gamma_{AC}\cup \Gamma_{CB}\subset \mathrm{St}(v,\Sigma), as desired.

Thus, for v \in \Sigma and A, B \in \Gamma \cap \mathrm{St}(v,\Sigma), we have \Gamma_{AB}\subset \Gamma \cap \mathrm{St}(v,\Sigma), finishing the proof that Γ is non-revisiting.

About these ads
This entry was posted in Convex polytopes, Guest blogger and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s