← All problems

Erdős Problem #190 — Monochromatic or rainbow arithmetic progression thresholds

47 years old · traced to

For an integer k≥2k\ge 2, write [N]={1,…,N}[N]=\{1,\ldots,N\}. A kk-term arithmetic progression in [N][N] is a sequence a,a+d,…,a+(k−1)da,a+d,\ldots,a+(k-1)d of integers with d≥1d\ge 1 and a+(k−1)d≤Na+(k-1)d\le N. A finite coloring is any map from [N][N] to a finite set of colors, with no fixed bound on the number of colors. The progression is monochromatic if all its terms have the same color, and rainbow if their colors are pairwise distinct. Define

H(k)=min⁡{N≥1: every finite coloring of [N] contains a monochromatic or rainbow k-term arithmetic progression}.H(k)=\min\bigl\{N\ge 1:\text{ every finite coloring of }[N]\text{ contains a monochromatic or rainbow }k\text{-term arithmetic progression}\bigr\}.

Estimate the growth of H(k)H(k); in particular, is it true that

lim⁡k→∞H(k)1/kk=∞?\lim_{k\to\infty}\frac{H(k)^{1/k}}{k}=\infty?

Erdős Problems #190

Background

This is a canonical Ramsey problem: instead of asking only for a monochromatic configuration, one allows the other canonical pattern in which every term has a different color. Erdős and Graham posed the growth question in their work on van der Waerden’s theorem and related topics. The existence of H(k)H(k) follows from Szemerédi’s theorem, as used in the canonical Ramsey argument. Erdős Problems #190 Three-color van der Waerden numbers grow super-exponentially

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.