Evasive properties of sparse graphs and some linear equations in primes
We give an unconditional version of a conditional, on the Extended Riemann Hypothesis, result of Babai, Banerjee, Kulkarni and Naik (2010) [1] on the evasiveness of sparse graphs on n nodes, provided that n is large enough. We also obtain a substantially stronger estimate that holds for almost all n. Our approach is based on some rather deep tools from analytic number theory: the BombieriVinogradov theorem, a result of Balog and Srkzy on prime divisors of sum-sets and a result Baker and Harman on large prime divisors of shifted primes.
evasiveness sparse graphs prime numbers