TY - JOUR

T1 - Evasive properties of sparse graphs and some linear equations in primes

AU - Shparlinski, Igor E.

PY - 2014/8/28

Y1 - 2014/8/28

N2 - 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 Bombieri-Vinogradov theorem, a result of Balog and Sárközy on prime divisors of sum-sets and a result Baker and Harman on large prime divisors of shifted primes.

AB - 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 Bombieri-Vinogradov theorem, a result of Balog and Sárközy on prime divisors of sum-sets and a result Baker and Harman on large prime divisors of shifted primes.

UR - http://www.scopus.com/inward/record.url?scp=84926417584&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2014.06.005

DO - 10.1016/j.tcs.2014.06.005

M3 - Comment/opinion

AN - SCOPUS:84926417584

VL - 547

SP - 117

EP - 121

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -