# Criterion for acyclicity of flag complexes

Let $$\Delta$$ be a flag complex on $$n$$ vertices. Let $$r$$ be the smallest size of the facets of $$\Delta$$. Suppose that $$2r>n$$. Must $$\Delta$$ be acyclic?

It looks to me like you can prove the stronger property of contractibility by induction, as follows. Let $$\Delta$$ be the independence complex of graph $$G$$, as guaranteed by the flag property.

If $$\Delta$$ is a cone, then $$\Delta$$ is contractible. This will be the base case, along with dimension 0 (where $$\Delta$$ has a single point) and dimension 1 (where $$\Delta$$ is a 1-simplex).

Otherwise, every vertex $$v$$ has degree at least 1 in $$G$$. Consider a fixed pair of vertices $$v,w$$ that are adjacent in $$G$$. We'll use that the link of $$v$$ in $$\Delta$$ is the independence complex of $$G \setminus N[v]$$ (and similarly for $$w$$). Now $$\operatorname{link}_\Delta v$$, $$\operatorname{link}_\Delta w$$ are contained in the independence complex of $$G \setminus \{v,w\}$$.

Since we remove at most one vertex from each maximal face in each case, $$r$$ goes down by at most one in each considered subcomplex, while the number of vertices goes down by at least 2. So by induction, $$\operatorname{link}_\Delta v$$, $$\operatorname{link}_\Delta w$$, and the independence complex of $$G \setminus {v,w}$$ are all contractible.

Now $$\Delta$$ is the union of the faces that contain $$v$$, those that contain $$w$$, and those that contain neither. So $$\Delta$$ is the union of the subcomplexes $$\Delta_1 = v*\operatorname{link} v$$, $$\Delta_2 = w*\operatorname{link} w$$, and $$\Delta_0$$ the independence complex of $$G \setminus \{v,w\}$$. It now follows by e.g. Lemma 10.4(ii) of Björner's Topological methods that $$\Delta$$ is contractible.

I didn't immediately see the answer to the question of whether there's a sensible generalization of some sort to non-flag complexes. The flag property is used above in where $$\operatorname{link}_\Delta v$$ is the independence complex of $$G \setminus N[v]$$; also in finding a pair of vertices that are in no common face.

(Updated over initial version to fix a problem with the facet sizes in the induction, in response to a comment of and off-MO discussion with @Hailong Dao.)

• Great, thanks Russ. This remind me of my paper with Jay, perhaps I should dig it out. – Hailong Dao Nov 19 '18 at 16:18
• Perhaps the non-evasiveness has to be addressed further given that the proof changed. 1) the ones described in the problem. 2) the ones obtained from removing a vertex, which give an additional local condition to relax the larger one, i.e there is a vertex with a pleasant link! It seems like this imposes many conditions on the graph. Do you have a systematic way to construct interesting examples? – José Alejandro Samper Dec 9 '18 at 20:55
• @JoséAlejandroSamper, as far as examples, look at the graph theory literature, under the name independent domination. A nontrivial example can be constructed by attaching a large number of pendant edges to each vertex of a complete graph. See e.g. Independent domination in graphs: a survey and recent results by Goddard and Henning. – Russ Woodroofe Dec 10 '18 at 12:14
• @JoséAlejandroSamper, I thought when I updated the post that I saw how to easily recover nonevasiveness, but now I no longer see it. I'll delete my earlier comment claiming that it holds. – Russ Woodroofe Dec 10 '18 at 12:37
• I still feel it should hold! Anyways, i like this property quite a bit. Do you know how close to tight is this? – José Alejandro Samper Dec 10 '18 at 17:27