Problem 54

A set of integers $A$ is Ramsey $2$ -complete if, whenever $A$ is $2$ -coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$ .

Burr and Erdős [BuEr85] showed that there exists a constant $c>0$ such that it cannot be true that

\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2

for all large $N$ and that there exists a Ramsey $2$ -complete $A$ such that for all large $N$

\lvert A\cap \{1,\ldots,N\}\rvert < (2\log_2N)^3.

Improve either of these bounds.

Source: erdosproblems.com/54

Number theory
Ramsey theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved, in the site's label, which marks a request carried out rather than a proposition proved: the sparsest Ramsey $2$ -complete sequence has counting function of order $(\log N)^2$ , by Theorem 1.1 of Conlon, Fox and Pham at $r=2$ , which improves the site's second display from the cube to the square of the logarithm and matches the first display up to the constant factor. The status-defining source is an arXiv preprint, arXiv:2104.14766v1 (30 April 2021); the site's curator accepted it as the resolution (SOLVED, last edited 28 October 2025), and the authors' refereed 2022 paper on Problem 1211 uses its Theorem 6.1 as an input. On the curator's acceptance the claim page records the result as accepted, with no refereed version, and the frontmatter standing is derived from it.

BuEr85: Burr, S. A. and Erdős, P., A Ramsey-type property in additive number theory. Glasgow Math. J. 27 (1985), 5--10; DOI 10.1017/S0017089500006029. Theorems 1 and 2 on printed p. 5, Theorems 1a, 2a and 1b on p. 6, Theorem 1c on p. 7. Library home: Burr and Erdős 1985; result pages Burr and Erdős 1985, Theorem 1 and Burr and Erdős 1985, Theorem 2.
CFP21: Conlon, D., Fox, J. and Pham, H. T., Subset sums, completeness and colorings. arXiv:2104.14766v1 (30 April 2021), 75 pp.; Theorem 1.1 and the paragraphs around it, p. 3. Library home: Conlon 2021; result page Conlon 2021, Theorem 1.1.
Er95: Erdős, P., Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas 2 (1995), 165--186; item 11 of Part I. The site cites p. 172 of the journal; the author's typescript, with its own running-head pages, has the item on its p. 7. Library home: Erdős 1995.
CFP22: Conlon, D., Fox, J. and Pham, H. T., The upper logarithmic density of monochromatic subset sums. Mathematika 68 (2022), no. 4, 1292--1301; arXiv:2105.15195v3. Context: a refereed paper whose Theorem 3 is Theorem 6.1 of [CFP21]. Library home: Conlon, Fox and Pham 2022.

Problem 54

Status

Proof claims

Discussion