Problem 531

Let $F(k)$ be the minimal $N$ such that if we two-colour $\{1,\ldots,N\}$ there is a set $A$ of size $k$ such that all subset sums $\sum_{a\in S}a$ (for $\emptyset\neq S\subseteq A$ ) are monochromatic. Estimate $F(k)$ .

Source: erdosproblems.com/531

Number theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

The site labels the problem OPEN. The bounds located in the search, whose scope the Current assessment records, are the doubly exponential lower bound $F(k)\ge2^{2^{k-1}/k}$ of Balogh, Eberhard, Narayanan, Treglown and Wagner (2017, refereed), which replaced Erdős and Spencer's $F(k)>2^{ck^2/\lg k}$ (1989), and Taylor's tower-type upper bound (1981, Corollary 3.4), $F(k)$ at most a tower of threes of height $4k-3$ . No source narrows the gap between them. This is a bounded negative finding, not a certificate of openness.

Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), North-Holland (1973), 117--138; p. 122. Library home: Erdos 1973.
ErSp89: Erdős, P. and Spencer, J., Monochromatic sumsets. J. Combin. Theory Ser. A 50 (1989), no. 1, 162--163. Library home: Erdős and Spencer 1989.
BENTW17: Balogh, J., Eberhard, S., Narayanan, B., Treglown, A. and Wagner, A. Z., An improved lower bound for Folkman's theorem. Bull. Lond. Math. Soc. 49 (2017), no. 4, 745--747, doi:10.1112/blms.12058; arXiv:1703.02473, v1 7 March 2017, v2 5 June 2017. Library home: Balogh et al. 2017.
Ta81: Taylor, A. D., Bounds for the disjoint unions theorem. J. Combin. Theory Ser. A 30 (1981), no. 3, 339--344, doi:10.1016/0097-3165(81)90031-5; Corollary 3.4 on p. 343 (PDF p. 5 of the publisher's open-archive file). Library home: Taylor 1981.
KLRSSV19: Komjáth, P., Leader, I., Russell, P. A., Shelah, S., Soukup, D. T. and Vidnyánszky, Z., Infinite monochromatic sumsets for colourings of the reals. Proc. Amer. Math. Soc. 147 (2019), no. 6, 2673--2684; arXiv:1710.07500. Context only (infinite sumsets $X+X$ in colorings of the reals); no library home; abstract only.

Problem 531

Status

Proof claims

Discussion