A lower bound for the recognition of digraph properties

The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case, Aanderaa and Rosenberg conjectured that there is a constant such that every digraph property which is monotone (not destroyed by the deletion of edges) and nontrivial (holds for some but not all digraphs) has complexity at leastv ² wherev is the number of nodes in the digraph. This conjecture was proved by Rivest and Vuillemin and a lower bound ofv ²/4–o(v ²) was subsequently found by Kahn, Saks, and Sturtevant. Here we show a lower bound ofv ²/2–o(v ²). We also prove that a certain class of monotone, nontrivial bipartite digraph properties is evasive (requires that every entry in the adjacency matrix be examined in the worst case).