{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T03:06:11Z","timestamp":1777777571041,"version":"3.51.4"},"reference-count":42,"publisher":"Emerald","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,5,16]]},"abstract":"<jats:p>Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in the early 1970s that all monotone graph properties are evasive\u2014that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.<\/jats:p>","DOI":"10.1561\/0400000055","type":"journal-article","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T09:47:13Z","timestamp":1368697633000},"page":"337-415","source":"Crossref","is-referenced-by-count":9,"title":["Evasiveness of Graph Properties and Topological Fixed-Point Theorems"],"prefix":"10.1108","volume":"7","author":[{"given":"Carl A.","family":"Miller","sequence":"first","affiliation":[{"name":"University of Michigan, Department of Electrical Engineering and Computer Science, 2260 Hayward St., Ann Arbor, MI 48109-2121","place":["USA"]}]}],"member":"140","published-online":{"date-parts":[[2013,5,16]]},"reference":[{"key":"2026040605562483300_ref001","first-page":"15","volume-title":"In Classical and New Paradigms of Computation and their Complexity Hierarchies","author":"Ambainis","year":"2004"},{"key":"2026040605562483300_ref002","volume-title":"Basic Abstract Algebra","author":"Ash","year":"2007"},{"key":"2026040605562483300_ref003","first-page":"71","article-title":"Evasiveness and the distribution of prime numbers","volume-title":"In Symposium on Theoretical Aspects of Computer Science","author":"Babai","year":"2010"},{"key":"2026040605562483300_ref004","first-page":"1","article-title":"A sharpened version of the Aanderaa-Rosenberg conjecture","volume-title":"Stichting Mathematisch Centrum. Zuivere Wiskunde","author":"Best","year":"1974"},{"key":"2026040605562483300_ref005","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(76)90021-6","article-title":"Complete subgraphs are elusive","volume":"21","author":"Bollobas","year":"1976","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2026040605562483300_ref006","first-page":"358","article-title":"Bounds for small-error and zero-error quantum algorithms","volume-title":"In Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"Buhrman","year":"1999"},{"key":"2026040605562483300_ref007","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1002\/rsa.20164","article-title":"Improved lower bounds on the randomized complexity of graph properties","volume":"30","author":"Chakrabati","year":"2007","journal-title":"Random Structures and Algorithms"},{"key":"2026040605562483300_ref008","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1137\/S0097539700382005","article-title":"Evasiveness of subgraph containment and related properties","volume":"31","author":"Chakrabati","year":"2002","journal-title":"SIAM Journal on Computing"},{"key":"2026040605562483300_ref009","first-page":"661","article-title":"Quantum query complexity of minor-closed graph properties","volume-title":"In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science","author":"Childs","year":"2011"},{"key":"2026040605562483300_ref010","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032916","volume-title":"Theory of Computational Complexity","author":"Du","year":"2000"},{"key":"2026040605562483300_ref011","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-45726-7_9","article-title":"Computing graph properties by randomized subcube partitions","volume-title":"In Randomization and Approximation Techniques in Computer Science","author":"Friedgut","year":"2002"},{"key":"2026040605562483300_ref012","first-page":"119","article-title":"On the randomized complexity of monotone graph properties","volume":"10","author":"Gr\u00f6ger","year":"1992","journal-title":"Acta Cybernetica"},{"key":"2026040605562483300_ref013","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF01206357","article-title":"An \u03c9(n43) lower bound on the randomized complexity of graph properties","volume":"11","author":"Hajnal","year":"1991","journal-title":"Combinatorica"},{"key":"2026040605562483300_ref014","volume-title":"Algebraic Topology","author":"Hatcher","year":"2002"},{"key":"2026040605562483300_ref015","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF01706081","article-title":"On the time required to detect cycles and connectivity in graphs","volume":"6","author":"Holt","year":"1972","journal-title":"Mathematical Systems Theory"},{"key":"2026040605562483300_ref016","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","article-title":"Efficient planarity testing","volume":"21","author":"Hopcroft","year":"1974","journal-title":"Journal of the ACM"},{"key":"2026040605562483300_ref017","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-75859-4","volume-title":"Simplicial Complexes of Graphs","author":"Jonsson","year":"2008"},{"key":"2026040605562483300_ref018","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579140","article-title":"A topological approach to evasiveness","volume":"4","author":"Kahn","year":"1984","journal-title":"Combinatorica"},{"key":"2026040605562483300_ref019","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF02122695","article-title":"A lower bound for the recognition of digraph properties","volume":"10","author":"King","year":"1990","journal-title":"Combinatorica"},{"key":"2026040605562483300_ref020","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01375470","article-title":"An \u03c9(n54) lower bound on the randomized complexity of graph properties","volume":"11","author":"King","year":"1991","journal-title":"Combinatorica"},{"key":"2026040605562483300_ref021","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1145\/800119.803888","article-title":"Determining graph properties from matrix representations","volume-title":"In Proceedings of Sixth Annual ACM Symposium on Theory of Computing","author":"Kirkpatrick","year":"1974"},{"key":"2026040605562483300_ref022","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0095-8956(80)90057-X","article-title":"Further results on the Aanderaa-Rosenberg conjecture","volume":"28","author":"Kleitman","year":"1980","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2026040605562483300_ref023","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1007\/s00493-010-2485-3","article-title":"An asymptotic bound for the complexity of monotone graph properties","volume":"30","author":"Korneffel","year":"2010","journal-title":"Combinatorica"},{"key":"2026040605562483300_ref024","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-71962-5","volume-title":"Combinatorial Algebraic Topology","author":"Kozlov","year":"2008"},{"key":"2026040605562483300_ref025","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0041-0","volume-title":"Algebra","author":"Lang","year":"2002","edition":"rev. 3rd"},{"key":"2026040605562483300_ref026","article-title":"Lecture notes on evasiveness of graph properties","volume-title":"arXiv","author":"Lovasz","year":"2002"},{"key":"2026040605562483300_ref027","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-7910-0","volume-title":"A Course in Topological Combinatorics","author":"Longueville","year":"2013"},{"key":"2026040605562483300_ref028","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-76649-0","volume-title":"Using the Borsuk-Ulam Theorem","author":"Matousek","year":"2008"},{"key":"2026040605562483300_ref029","first-page":"471","article-title":"On the computational complexity of graph theoretical properties","volume-title":"In Proceedings of the Fifth British Combinatorial Conference","author":"Milner","year":"1975"},{"key":"2026040605562483300_ref030","volume-title":"Elements of Algebraic Topology","author":"Munkres","year":"1984"},{"key":"2026040605562483300_ref031","first-page":"31","article-title":"Every decision tree has an influential variable","volume-title":"In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science","author":"O\u2019Donnell","year":"2005"},{"key":"2026040605562483300_ref032","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02565743","article-title":"Fixed-point sets of group actions on finite acyclic complexes","volume":"50","author":"Oliver","year":"1975","journal-title":"Commentarii mathematici Helvetici"},{"key":"2026040605562483300_ref033","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/0304-3975(76)90053-0","article-title":"On recognizing graph properties from adjacency matrices","volume":"3","author":"Rivest","year":"1976","journal-title":"Theoretical Computer Science"},{"key":"2026040605562483300_ref034","first-page":"15","article-title":"On the time required to recognize properties of graps: A problem","volume-title":"SIGACT News","author":"Rosenb erg","year":"1973"},{"key":"2026040605562483300_ref035","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2371271","article-title":"Fixed-point theorems for periodic transformations","volume":"63","author":"Smith","year":"1941","journal-title":"American Journal of Mathematics"},{"key":"2026040605562483300_ref036","first-page":"286","article-title":"Graph properties and circular functions: How low can quantum query complexity go?","volume-title":"In Proceedings of the IEEE Annual Conference on Computation Complexity","author":"Sun","year":"2004"},{"key":"2026040605562483300_ref037","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/S009753979119415X","article-title":"Some results on elusive graph properties","volume":"23","author":"Triesch","year":"1994","journal-title":"SIAM Journal on Computing"},{"key":"2026040605562483300_ref038","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01844851","article-title":"On the recognition complexity of some graph properties","volume":"16","author":"Triesch","year":"1996","journal-title":"Combinatorica"},{"key":"2026040605562483300_ref039","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0012-365X(99)00049-7","article-title":"Constructions preserving evasiveness and collapsibility","volume":"207","author":"Welker","year":"1999","journal-title":"Discrete Mathematics"},{"key":"2026040605562483300_ref040","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/0217031","article-title":"Monotone bipartite graph properties are evasive","volume":"17","author":"Yao","year":"1988","journal-title":"SIAM Journal on Computing"},{"key":"2026040605562483300_ref041","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0022-0000(91)90003-N","article-title":"Lower bounds to randomized algorithms for graph properties","volume":"42","author":"Yao","year":"1991","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040605562483300_ref042","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1080\/00029890.1997.11990704","article-title":"Newman\u2019s short proof of the prime number theorem","volume":"104","author":"Zagier","year":"1997","journal-title":"American Mathematical Monthly"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/7\/4\/337\/11490814\/0400000055en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/7\/4\/337\/11490814\/0400000055en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:16Z","timestamp":1777489276000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/7\/4\/337\/1332202\/Evasiveness-of-Graph-Properties-and-Topological"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,16]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5,16]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000055","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,16]]}}}