Further results on the Aanderaa-Rosenberg conjecture

Some results on the “evasiveness” of graph properties are obtained, extending the work of Rivest and Vuillemin. In particular, it is shown that any nontrivial monotone graph property on n vertices is at least $\text{n}{}^2\text{9}\text{-}\text{evasive}$; particular stronger results are obtained for values of n that are powers of primes less than 14. A new result allowing interpolation among n values is obtained, as are some stronger results on restricted classes of properties.