A topological approach to evasiveness (Q1065831)

The authors consider the evasiveness problem for finite graphs. This problem was introduced in 1973 with the Aanderaa-Rosenberg conjecture, and a partial solution was solved in 1978 by Rivest and Vuillemin. The problem deals with the algorithmic determination of graph properties for graphs given by their adjacency matrix. In order to know the entire graph all entries in the matrix must be probed. Other graph representations like an adjacency list do not have this property since the end of some list yields the information that all other edges which might have been there are actually not there. This then leads to the question whether for determining a graph property the entire graph must be known or whether the property can be decided already on partial information obtained after a suitable collection of probes in the adjacency matrix. Aanderaa and Rosenberg conjectured that for nontrivial monotone graph properties at least a positive fraction \(c.n^ 2\) of the entries of the adjacency matrix must be probed. In this form the conjecture has been proved. What remains is the question whether under the same condition all edges must be probed (in which case the property is called evasive), and the present paper presents after many years another step to the solution of that problem. The authors provide a positive answer for graphs on a prime power number of vertices; they also solve the case for six vertices. What makes the paper interesting is the fact that the proof is based on non-trivial results from algebraic and combinatorial geometry. The graph problem is considered a set problem (based on the set of all possible edges), and this set problem is considered as a simplicial complex. On such complexes properties like collapsibility, contractibility and properties of homology groups like acyclicity are investigated, leading to further versions of the strengthened Aanderaa Rosenberg conjecture. The connection goes as follows: nonevasive properties lead to collapsible simplicial complexes; Collapsible complexes are acyclic. In combination with the fact that this complex is invariant under a transitive automorphism group it can be shown for special cases that an acyclic complex invariant under a transitive group is the full simplex, which implies that the property is trivial. This solves the problem for the special case.