A Lower Bound for the Complexity of Monotone Graph Properties
Robert Scheidweiler, Eberhard Triesch · SIAM Journal on Discrete Mathematics · 2013
More than 30 years ago, Karp conjectured that all nontrivial monotone graph properties are evasive, i.e., have decision tree complexity $\binom{n}{2}$, where $n$ is the number of vertices. It was proved in 1984 by Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297--306] if $n$ is a prime power by a topological approach. Using their method, we prove a lower bound of $\frac{1}{3}n^2-o(n^2)$ for general $n$.