Evasiveness of Abstract Simplicial Complexes

As we have seen in the previous section, some of the most important results concerning evasiveness were obtained by topological methods. As a matter of fact, the whole concept can be extended to a purely simplicial context, as the next definition shows. 

In the situation described in Definition 13.6(2), we say that the abstract simplicial complex X ME-redwces to its subcomplex Y. The following facts about NE-reduction are useful for our arguments 

Statement (1) follows from the fact that if v is any vertex of an abstract simplicial complex X, then we have the equalities Ikx = (Ikx ) Y and 

To see statement (2) we can first prove that a nonevasive abstract simplicial complex is collapsible. Perhaps the simplest argument is to use induction on the number of vertices. Indeed, if our abstract simplicial complex has one vertex, then it must be nonempty and is therefore collapsible. For the induction step we notice that for any abstract simplicial complex X and any vertex V of X, if both lkx( ) and dlx(v) are collapsible, then so is X. To find a collapsing sequence for X, start by collapsing away all the simplices that contain n, following some collapsing sequence for lkx( ). This will remove the open star of n, and we can finish off by continuing with any collapsing sequence for dlx(r ). 

The full generality of statement (2) follows now from the definition of NE-reduction and the fact that the open star of v can be collapsed away as long as the link of v is collapsible. 

---