Evasiveness of Subgraph Containment and Related Properties

We prove new results on evasiveness of monotone graph properties by extending the techniques of Kahn, Saks, and Sturtevant [ Combinatorica, 4 (1984), pp. 297--306]. For the property of containing a subgraph isomorphic to a fixed graph, and a fairly large class of related n-vertex graph properties, we show evasiveness for an arithmetic progression of values of n. This implies a $\frac12n^2 - O(n)$ lower bound on the decision tree complexity of these properties.We prove that properties that are preserved under taking graph minors are evasive for all sufficiently large n. This greatly generalizes a theorem due to Best, van Emde Boas, and Lenstra [A Sharpened Version of the Aanderaa--Rosenberg Conjecture, Report ZW 30/74, Mathematisch Centrum, Amsterdam, The Netherlands, 1974] which states that planarity is evasive. We prove a similar result for bipartite subgraph containment.