Carl A. Miller (2013), "Evasiveness of Graph Properties and Topological Fixed-Point Theorems", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 7: No. 4, pp 337-415. http://dx.doi.org/10.1561/0400000055

© 2013 C. A. Miller

Computational aspects of combinatorics and graph theory, Computational complexity, Computational Models and Complexity

Download article
**In this article:**

1. Introduction

2. Basic Concepts

3. Chain Complexes

4. Fixed-Point Theorems

5. Results on Decision-Tree Complexity

A. Appendix

Acknowledgments

References

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āthat 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.

Preface

1. Introduction

2. Basic Concepts

3. Chain Complexes

4. Fixed-point theorems

5. Results on Decision-Tree Complexity

A. Appendix

Acknowledgements

References

*Evasiveness of Graph Properties and Topological Fixed-Point Theorems* addresses a fascinating topic that lies at the interface between mathematics and theoretical computer science. There have been several interesting research
papers that use topological methods to prove lower bounds on the complexity of graph properties. The goal of this text is to offer an
integrated version of the underlying proofs in this body of research. While there are a number of very good expositions available on
topological methods in decision-tree complexity, they all refer to other sources for the proofs of some topological results. This work is the
first that provides a completely self-contained account. *Evasiveness of Graph Properties and Topological Fixed-Point Theorems* begins by laying
out the important foundational material and builds up to the more complex results at a steady pace. The capstone results, which consist of
three lower bounds on the complexity of graph properties, appear in the final part of the text. The reader is not assumed to have any prior
background in algebraic topology as all constructions from that subject are developed from scratch. The only prerequisite is a high level of
comfort with discrete mathematics and linear algebra.