Evasive properties of sparse graphs and some linear equations in primes

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalComment/opinionpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)117-121
Number of pages5
JournalTheoretical Computer Science
Volume547
DOIs
Publication statusPublished - 28 Aug 2014

Fingerprint Dive into the research topics of 'Evasive properties of sparse graphs and some linear equations in primes'. Together they form a unique fingerprint.

Cite this