Logo
All Random Solved Random Open
OPEN
Let $g(n)$ be maximal such that given any set $A\subset \mathbb{R}$ with $\lvert A\rvert=n$ there exists some $B\subseteq A$ of size $\lvert B\rvert\geq g(n)$ such that $b_1+b_2\not\in A$ for all $b_1\neq b_2\in B$.

Estimate $g(n)$.

A conjecture of Erdős and Moser. Klarner proved $g(n) \gg \log n$ (indeed, a greedy construction suffices). Choi [Ch71] proved $g(n) \ll n^{2/5+o(1)}$. The current best bounds known are \[(\log n)^{1+c} \ll g(n) \ll \exp(\sqrt{\log n})\] for some constant $c>0$, the lower bound due to Sanders [Sa21] and the upper bound due to Ruzsa [Ru05]. Beker [Be25] has proved \[(\log n)^{1+\tfrac{1}{68}+o(1)} \ll g(n).\]