👁 Logo

Forum Inbox Favourites Tags

Forum

A problem of Erdős, Nešetřil, and Rödl.

A negative answer was given by Reiher, Rödl, and Sales [RRS24], who proved that, for any $0<\mu<1/2$, there exists $A\subseteq \mathbb{N}$ such that every finite colouring of $A$ contains a three-term arithmetic progression, and yet every subset of $A$ of size $n$ contains a subset of size $\geq \mu n$ without a three-term arithmetic progression.

See also [774] and [846].

View the LaTeX source

This page was last edited 27 January 2026. View history

External data from the database - you can help update this
Formalised statement? Yes

Likes this problem	Dogmachine
Interested in collaborating	None
Currently working on this problem	None
This problem looks difficult	None
This problem looks tractable	None
The results on this problem could be formalisable	None
I am working on formalising the results on this problem	None

• In fact, the paper shows $0<\mu<2/3$ and any $\mu>2/3$ cannot hold (consider subsets of size three that form a 3-AP).

  Adenwalla — 11:26 on 16 Feb 2026

• Can this problem appear in the front page since It was disproved already?

  (The site has been updated to address this comment.)
  Dogmachine — 00:21 on 27 Jan 2026

• My colleague Andrew Xu has produced a GPT 5.2 Pro response that claims the problem is solved negatively in a paper by Reiher-Rodl-Sales ("Colouring versus density in integers and Hales-Jewett cubes," arXiv:2311.08556): https://chatgpt.com/share/696d3236-3d78-8009-905f-0606c66b1efa

  (The site has been updated to address this comment.)
  Neel Somani — 09:41 on 19 Jan 2026

  • Confirmed. Theorem 1.4 shows for any $k \ge 3$ (here we take $k=3$) and $0 < \varepsilon < (k-1)/k$, there is an $A \subset \mathbb{N}$ such that (a) any subset of $A$ of size $n$ contains a subset of size $\varepsilon n$ with no $k$-term AP; (b) for every $r \ge 1$ and every $r$-coloring of $A$, there is a monochromatic $k$-term AP.

    natso26 — 13:19 on 19 Jan 2026