Evasive graph property

Definition 13.3. A graph property Q of graphs onn vertices is called evasive if in the worst case we need to ask (2) questions in the course of the algorithm described above. Otherwise, the graph property is called nonevasive. 

Every nontrivial monotone graph property for graphs on n vertices is evasive. 

Assume now that n = p, for some prime number p. Assume that the Evasiveness Conjecture is false for that value of n, and let Q denote a monotone, but nonevasive, graph property. Furthermore, let GF(n) denote a field with n elements, which exists because n is a prime power, and let GF(n) denote the multiplicative group of that field. Let F be a subgroup of [Pg.228]

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

---