A topological approach to evasiveness

Jeff Kahn, Michael Saks, Dean Sturtevant

Research output: Contribution to journalArticlepeer-review

102 Scopus citations


The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the graph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity Ω(v 2) where v is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper the truth of Karp's conjecture is shown to follow from another conjecture concerning group actions on topological spaces. A special case of the conjecture is proved which is applied to prove Karp's conjecture for the case of properties of graphs on a prime power number of vertices.

Original languageEnglish (US)
Pages (from-to)297-306
Number of pages10
Issue number4
StatePublished - Dec 1984

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


  • AMS subject classification (1980): 05C99, 55U05


Dive into the research topics of 'A topological approach to evasiveness'. Together they form a unique fingerprint.

Cite this