Problem 781

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$ ?

Source: erdosproblems.com/781

Additive combinatorics

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The status-defining source is Theorem 1.1 of Alon and Spencer [AlSp89] (J. Combin. Theory Ser. A 52 (1989), 275--287, refereed): $c_1k^3\le f(k)\le c_2k^3$ for constants $c_1,c_2>0$ and all $k$ , so $f(k)=k^2-k+1$ fails for every large $k$ and $f(k)$ is known up to constant factors. Brown, Erdős and Freedman [BEF90] had shown $k^2-k+1\le f(k)\le(k^3-4k+9)/3$ and asked whether the lower bound is exact. The claim page is Alon and Spencer (accepted on the refereed publication and the site's credit).

Problem 781

Status

Proof claims

Discussion