A Caltech Library Service

Independent arithmetic progressions

Conlon, David and Fox, Jacob and Sudakov, Benny (2019) Independent arithmetic progressions. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
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)).
Funding AgencyGrant Number
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
Swiss National Science Foundation (SNSF)200021-175573
Record Number:CaltechAUTHORS:20190819-170939635
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98034
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 23:08
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page