5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Great, thanks Russ. This remind me of my paper with Jay, perhaps I should dig it out. $\endgroup$ – Hailong Dao Nov 19 '18 at 16:18
  • $\begingroup$ 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? $\endgroup$ – José Alejandro Samper Dec 9 '18 at 20:55
  • $\begingroup$ @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. $\endgroup$ – Russ Woodroofe Dec 10 '18 at 12:14
  • $\begingroup$ @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. $\endgroup$ – Russ Woodroofe Dec 10 '18 at 12:37
  • $\begingroup$ I still feel it should hold! Anyways, i like this property quite a bit. Do you know how close to tight is this? $\endgroup$ – José Alejandro Samper Dec 10 '18 at 17:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.