The Complexity of Monotone Graph Properties

efine the term "graph property" to simply mean a function which assigns to any graph of order n an element of the set {0, 1}. We can measure the complexity of such a function by determining the minimum possible depth of a decision-tree which computes it. If the minimum possible depth is n(n-1)/2 (the worst possible case), then we say that the graph property is evasive. It is conjectured that all graph properties which are monotone increasing (i.e., properties that are never lost when new edges are added to a graph) are evasive. This conjecture has existed for at least 35 years and is still open. In this talk I will discuss one of the partial results that is known for this conjecture. The result (from the paper "a topological approach to evasiveness" by Kahn, Saks, and Sturtevant, 1984) asserts that the conjecture is true if n is a power of a prime. The proof of the result involves an elegant application of algebraic topology.