Evasive abstract simplicial complex

The following is a very important conjecture about evasive abstract simplicial complexes, which has now been open for quite some time. 

A finite nonempty abstract simplicial complex X is called nonevasive if either X is a point, or, inductively, there exists a vertex v ofX such that both X ti andlkxv are nonevasive. Otherwise, the complex X is called evasive. 

Conjecture 13.8. (Evasiveness Conjecture for abstract simplicial complexes) Let X be a nonempty abstract simplicial complex with the vertex set [n]. Assume furthermore that T is a subgroup of [Pg.230]

The Evasiveness Conjecture for abstract simplicial complexes is still open for general n. It has been verified for the case when n is a prime power, as well as for the special cases n = 6, 10, and 12. 

Definition 13.6(1) can be reinterpreted algorithmically as follows we know a certain abstract simplicial complex X, and there is some chosen subset a of the set of vertices of X that we do not know. We need to decide whether a is a simplex of X by asking the oracle questions of the type is v in a where v is some vertex of X. The abstract simplicial complex X is then called evasive if in the worst case scenario, we may have to ask this question for all vertices of X. 

Proposition 13.9. A monotone graph property Q is evasive if and only if the associated abstract simplicial complex A Q) is evasive. 

---