Evasiveness of Graph Properties and Topological Fixed-Point Theorems

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.