- A-269 (TAP Seminar Room)
We confirm the evasiveness of several monotone graph properties under widely accepted number theoretic hypotheses (e.g. Generalized Riemann Hypothesis, Chowla's Conjecture on smallest Dirichlet primes etc). In particular, we show:
(a) forbidden subgraph is evasive for all large enough n
(b) any montone property of sparse graphs (
Even our weaker unconditional results rely on some deep and interesting properties of the integers such as Vinogradov's theorem on Goldbach conjecture asserting that every odd integer can be expressed as the sum of three primes. Our main technical contribution here is in connecting the topological framework of Kahn, Saks and Sturtevant 84,(further developed by Chakrabarti, Khot and Shi 02), to analytic number theory via better analysis (e.g. using Weil's character sum estimates) of the orbital structure of permutation groups and their connection to the distribution of prime numbers (this is a joint work with Laci Babai, Anandam Banerjee and Vipul Naik).