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
SN - 0304-3975
VL - 547
SP - 117
EP - 121
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -