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

Abstract

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 $|A|\ge n/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.

14 pages