The Aanderaa–Karp–Rosenberg conjecture is that any non-trivial monotone property on graphs is evasive. It has been proved for several special cases, but for a general graph on $n$ vertices, we only known that $\Omega(n^2)$ queries are always needed.
Is it possible that for every monotone graph property at least $\binom n2-1$ queries are needed and this is sharp?
It is easy to see that this cannot happen for properties that, instead of graphs, act on an arbitrary transitive base set, as in that case a counterexample $f$ on $k$ variables can be blown up by defining $g=f\circ f$ on $k^2$ variables.
