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 January 2019 | Submitted
Journal Article Open

Lines in Euclidean Ramsey Theory


Let ℓ_m be a sequence of m points on a line with consecutive points of distance one. For every natural number n, we prove the existence of a red/blue-coloring of E^n containing no red copy of ℓ_2 and no blue copy of ℓ_m for any m ≥ 2^(cn). This is best possible up to the constant c in the exponent. It also answers a question of Erdős et al. (J Comb Theory Ser A 14:341–363, 1973). They asked if, for every natural number n, there is a set K ⊂ E^1 and a red/blue-coloring of E^n containing no red copy of ℓ_2 and no blue copy of K.

Additional Information

© The Author(s) 2018. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. Received 5 May 2017; revised 31 January 2018; accepted 25 February 2018; published online 23 March 2018. D. Conlon: Research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. J. Fox: Research supported by a Packard Fellowship and by NSF Career Award DMS-1352121. This paper was written while both authors were visiting the Simons Institute for the Theory of Computing in Berkeley and we are grateful for their generous support. The authors would also like to thank Noga Alon and Ben Green for helpful discussions. Finally, we wish to thank David Ellis, Ron Graham and an anonymous referee for a number of useful comments and corrections. In particular, the anonymous referee was the one to point us to the paper by Szlam [14], helping us to greatly improve the results in the concluding remarks.

Attached Files

Submitted - 1705.02166.pdf


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

Additional details

August 22, 2023
October 18, 2023