Nonevasive graph property

By a simple induction on the number of vertices, it will follow that if Q is a nonevasive graph property, then the abstract simplicial complex A Q) is collapsible see Proposition 13.7 and Proposition 13.9. 

It is not all too trivial to construct nonevasive graph properties. One example of such a property is being a so-called scorpion graph. Here a graph G on n vertices is called scorpion if it has 3 vertices s, t, and b such that... 

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]

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. 

Since the total number of queries is linear in the number of vertices, we see that for sufficiently large n we will need substantially fewer than (2) questions. In particular, this graph property is nonevasive. 

Since the graph property Q is nonevasive, we know that the abstract simplicial complex A Q) is collapsible see Proposition 13.7(2). In particular, it has to be Zp-acyclic. We can now use Theorem 13.5 to conclude that x A Q)r) = 1- On the other hand, the group F acts doubly transitively on the set [n], i.e., any ordered pair of points can mapped to any other ordered pair of points by a transformation from F. This means that the group F acts transitively on the set of vertices of the abstract simplicial complex A Q). Therefore, the only point of A G) that can possibly be fixed by every element in F is the barycenter of the simplex on all (") vertices, which of course can be the case only when A(Q) is a full simplex. This contradicts our assumption that the graph property Q is nontrivial. ... 

---