A topological approach to evasiveness
type: Item
instance of: scholarly article
title: A topological approach to evasiveness
zbMATH Open document ID: 0577.05061
DOI: 10.1007/BF02579140
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: 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 simpl…
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 55N99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3922711
zbMATH Keywords: evasive properties
zbMATH Keywords: evasive graph properties
zbMATH Keywords: Aanderaa-Rosenberg conjecture
zbMATH Keywords: graph properties
zbMATH Keywords: adjacency matrix
zbMATH Keywords: collapsible simplicial complexes
zbMATH Keywords: acyclic
author: J. Kahn
author: Michael Saks
author: Dean G. Sturtevant
reviewed by: Peter van Emde Boas
MaRDI profile type: Publication
cites work: Q4046079
cites work: Complete subgraphs are elusive
cites work: Q5614468
cites work: Q5772619
cites work: Q4131000
cites work: Fixed-point sets of group actions on finite acyclic complexes
cites work: On recognizing graph properties from adjacency matrices
cites work: Q4133137
cites work: Fixed-Point Theorems for Periodic Transformations
description: scientific article; zbMATH DE number 3922711