Published August 20, 2019
| Submitted
Report
Open
Independent arithmetic progressions
- Creators
-
Conlon, David
- Fox, Jacob
- Sudakov, Benny
Abstract
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
1901.05084.pdf
Files
(91.3 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:90c0688622c02324c457993ba4db7d07
|
91.3 kB | Preview Download |
Additional details
- Eprint ID
- 98034
- Resolver ID
- CaltechAUTHORS:20190819-170939635
- 676632
- European Research Council (ERC)
- David and Lucile Packard Foundation
- DMS-1352121
- NSF
- 200021-175573
- Swiss National Science Foundation (SNSF)
- Created
-
2019-08-20Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field