Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 20, 2019 | Submitted
Report Open

Independent arithmetic progressions


We show that there is a positive constant c such that any graph on vertex set [n] with at most cn^(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.

Additional Information

Conlon research supported by ERC Starting Grant 676632. Fox research supported by a Packard Fellowship and by NSF Career Award DMS-1352121. Sudakov research supported in part by SNSF grant 200021-175573. This note was first written in May 2015, predating a recent paper of Geneson [A note on long rainbow arithmetic progressions, arXiv:1811.07989] showing that T_k ≤ k^((5/2) + o(1)), and will form part of the forthcoming paper Short proofs of some extremal results III. We would like to thank Kevin Ford for some helpful discussions. We would also like to mention that recently József Balogh, Will Linz and Mina Nahvi independently investigated the question of estimating T_k and showed that T_k = k^(2 + o(1)).

Attached Files

Submitted - 1901.05084.pdf


Files (91.3 kB)
Name Size Download all
91.3 kB Preview Download

Additional details

August 19, 2023
October 18, 2023