Independent arithmetic progressions

Abstract

We show that there is a positive constant $c$ such that any graph on vertex set $[n]$ with at most $c{n}^2/k^2\log k$ edges contains an independent set of order $k$ whose vertices form an arithmetic progression. We also present applications of this result to several questions in Ramsey theory.

4 pages