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.

  • $\begingroup$ Quick comment that AKR is known to be true when $n$ is a prime power. The necessity of $n$ being a prime power is more due to the tools (cohomology) used in the proof rather than anything fundamental about graphs with a prime power number of edges. $\endgroup$
    – Arkady
    Oct 29, 2022 at 20:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.