Dense ascending waves: A resolution of the Alon-Spencer conjecture

For a positive integer $n$, write $[n]=\{1,\dots ,n\}$. A strictly increasing sequence of integers $x_1<\cdots <x_k$ is an \emph{ascending wave} if its consecutive differences are nondecreasing. Let $g(n)$ be the largest integer $k$ such that every set $A\subseteq [n]$ with $\mathrm{\mid }A\mathrm{\mid }\ge n\mathrm{/}2$ contains an ascending wave of length $k$. Alon and Spencer proved that $$c_1\frac{(\log n{)}^2}{\log \log n}\le g(n)\le c_2(\log n{)}^2$$ for all sufficiently large $n$, and they conjectured that the factor $\log \log n$ in the lower bound can be removed. In this paper, we confirm their conjecture.