Erdős Problem #129 — Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy of $K_k$ in at least one of the $r$ colours.

Erdős and Gyárfás asked whether the Ramsey quantity in the statement is at most exponential in the square root of the target set size. The reference formulation is false; the intended alternative formulation is unclear.

Known results

• Erdős and Gyárfás proved a lower bound of the form $R(n;3,r)>C^{\sqrt{n}}$.
• Antonio Girao observed that random two-colourings give $R(n;3,2)\ge C^n$, disproving the printed upper bound.

Claimed all-colour extension

A submitted probabilistic construction using Steiner triple systems and a union bound claims that, for every fixed $r\ge 2$, one has $R(n;3,r)\ge e^{c_r n}$ for infinitely many $n$. The argument is presented as generated by GPT-5.2 and has not been independently verified.

Current status (as of September 2026): The printed statement is settled false for $r=2$; the stronger claim for every fixed $r\ge 2$ is unverified, and the intended formulation remains unclear.