We call an n-vertex graph "sparse" if its number of edges is O(n). A graph property is said to be ''evasive'' if, in order to decide its membership, one needs to query all {n \choose 2} possible edges in wosrt case. Karp conjectures that any non-trivial monotone graph property must be evasive. It is a longstanding open question. We prove Karp's conjecture when restricted to 'sparse' graphs, i.e., we show that any non-trivial monotone decreasing property of n-vertex 'sparse' graphs is 'evasive' for all large enough n.

We use the topological approach proposed by Kahn, Saks and Sturtevant [1984] as a black box. The extra component of our method is a further connection to analytic number theory. In particular, we construct new group actions which rely crucially on some deep and interesting properties of the numbers. Under the Generalized Reimann Hypothesis, we can further stregthen our result to show that any monotone property of ''weakly sparse'' graphs is evasive, where 'weakly sparse' means that the number of edges are bounded by O(n^{5/4 - \epsilon}). We give an evidence that this can be further improved to O(n^3/2) but these bounds are far from the desired {n \choose 2} bound.

This is a joint work with Anandam Banerjee, Department of Mathematics, Northeastern University and Vipul Naik, Department of Mathematics, University of Chicago.