---

Claim. For $C = 2$, $C = 3$, every $C = 2^s$ and every $C = \tfrac12\binom{2s}{s}$, $s = 1, 2, \ldots$, there is a set $A \subseteq \mathbb N$ in which every $n$ has at most $C$ representations $n = x + y$ with $x, y \in A$, counted without regard to order and with $x = y$ counted once, and some $n$ has exactly $C$, such that in every partition of $A$ into finitely many parts one part again has some $n$ with exactly $C$ representations. In every construction the $C$ representations of such an $n$ are sums of two distinct elements, so dropping the sums $x + x$ leaves at most $C$ representations of every $n$ and exactly $C$ at that $n$: the same sets answer the corrected Statement of Problem 328, whose count $f$ takes only sums of two distinct elements. The answer to the corrected Statement is therefore no for these values of $C$, whether or not $t$ may depend on $A$. The constructions take $n_1 < n_2 < \cdots$ with $n_{i+1} \geq 4 n_i$, so that an integer is a sum of distinct $n_i$ in at most one way. For $C = 3$ (Theorem 1), $A$ is the set of sums $n_i + n_j$ with $i \neq j$: a sum of four distinct $n_i$ has exactly three representations, and a finite partition of $A$ colors the edges of the complete graph on the $n_i$, in which Ramsey's theorem gives an infinite monochromatic complete subgraph, whose edge sums lie in one part. Theorem 1' treats the other values: for $C = 2$ the sums $n_i + n_j$ with $i \not\equiv j \pmod 2$, where a finite coloring of an infinite complete bipartite graph has a monochromatic $C_4$; for $C = 2^s$ the sums of $s + 1$ of the $n_i$ whose indices form a complete residue system modulo $s + 1$; and for $C = \tfrac12\binom{2s}{s}$ the sums of $s$ distinct $n_i$, with Ramsey's theorem for $s$-tuples. The paper states the general conjecture, for every $k$, that Nešetřil and Rödl proved (claim page), and its note added in proof records their proof. The source is P. Erdős, Some applications of Ramsey's theorem to additive number theory, European Journal of Combinatorics 1 (1980), no. 1, 43–46, whose source card is Erdős 1980; the issue is dated March 1980 without a day, so the page is named by the first of that month.

Covers. The values $C = 2$, $3$, $2^s$ and $\tfrac12\binom{2s}{s}$ for $s \geq 1$. The paper says its methods should apply to other values of $k$ but doubts that they work for every $k$, and cannot settle $k = 5$. Every integer $C \geq 2$ is Nešetřil and Rödl's, on their claim page.

Depends on. Nothing in this wiki: the constructions are the paper's own, resting on Ramsey's theorem.

Acceptance. Refereed: European Journal of Combinatorics 1 (1980), no. 1, 43–46, the DOI linked above. Reviewed is not listed. The site's label settles the problem, and its commentary credits the full answer to Nešetřil and Rödl. The commentary (page last edited 6 April 2026) credits this paper only with the earlier answer for $C = 3$, $4$ and infinitely many other values, and the problem lists no parts, so that credit is not acceptance. Theorem 1′ also covers $C = 2$.