DISPROVED
This has been solved in the negative.
Let $f(k)$ be the minimal $n$ such that any $2$-colouring of $\{1,\ldots,n\}$ contains a monochromatic $k$-term descending wave: a sequence $x_1<\cdots <x_k$ such that, for $1<j<k$,\[x_j \geq \frac{x_{j+1}+x_{j-1}}{2}.\]Estimate $f(k)$. In particular is it true that $f(k)=k^2-k+1$ for all $k$?
A question of Brown, Erdős, and Freedman
[BEF90], who proved\[k^2-k+1\leq f(k) \leq \frac{k^3-4k+9}{3}.\]Resolved by Alon and Spencer
[AlSp89] who proved that in fact $f(k) \gg k^3$.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #781, https://www.erdosproblems.com/781, accessed 2026-02-13
