Monotone Bipartite Graph Properties are Evasive

A Boolean function P from $\{ {0,1} \}^\prime $ into $\{ {0,1} \}$ is said to be evasive, if every decision-tree algorithm for evaluating P must examine all t arguments in the worst case. It was known that any nontrivial monotone bipartite graph property on vertex set $V \times W$ must be evasive, when $|V| \cdot |W|$ is a power of a prime number. In this paper, we prove that every nontrivial monotone bipartite graph property is evasive.