Theory Seminar

The Complexity of Monotone Graph Properties

Carl Miller

Friday, October 01, 2010
10:30am - 11:30am
Beyster Bldg. 3941

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): Seth Pettie

Open to: Public