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} l o g 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.

This page was built for publication: Independent arithmetic progressions