Problem Statement
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$?
Categories:
Additive Combinatorics
Progress
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$.Source: erdosproblems.com/781 | Last verified: January 16, 2026