Skip to content

Erdős Problem #183

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: graph theory, ramsey theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Colour every edge of the complete graph \(K_N\) with one of \(k\) colours. Define \(R(3;k)\) as the least \(N\) such that every such colouring contains three vertices whose three connecting edges have one colour: a monochromatic triangle.

Erdős asked whether the exponential growth rate has a limit and what that limit is:

\[ \lim_{k\to\infty} R(3;k)^{1/k}. \]

Unlike the off-diagonal two-colour Ramsey number \(R(3,k)\), the semicolon in \(R(3;k)\) denotes a \(k\) colour diagonal triangle problem. Confusing these two functions would change the asymptotic problem entirely.

A small example

For one colour, \(R(3;1)=3\). For two colours, \(R(3;2)=6\): every two-colouring of \(K_6\) has a monochromatic triangle, whereas \(K_5\) admits a red five-cycle and its blue complementary five-cycle with no monochromatic triangle.

For higher \(k\), deleting one vertex from a colouring and using its incident-edge colour classes gives the standard recurrence

\[ R(3;k)\le 2+k\bigl(R(3;k-1)-1\bigr). \]

Iterating yields a factorial upper bound, not a constant-base exponential bound.

What is known

The existence and finite value of the proposed limit remain OPEN in the maintained #183, updated April 2026. Xu, Xie and Chen's refinement gives

\[ R(3;k)\le (e-1/6)\,k!+1. \]

The strongest lower estimate listed in that source, from Ageron, Casteras, Pellerin, Portella, Rimmel and Tomasik (2021) via Schur numbers, is

\[ R(3;k)\ge 380^{k/5}-O(1), \]

giving a limiting lower exponential base at least \(380^{1/5}\approx3.28\). A factorial upper bound has an unbounded \(k\) th root and cannot establish finiteness of the limit; the exponential lower bound cannot establish that the limit exists.

Status discrepancy: the pinned August 2025 catalogue labels #183 SOLVED, while the live April 2026 page labels the above unresolved limit OPEN. The historical attribution itself is questioned in the source discussion: the original 1961 Erdős reference may concern Schur numbers rather than the exact multicolour Ramsey formulation. Neither issue can be settled by changing a label alone.

GCL's current state

Original issue: #1452. Record PINNED SOLVED / LIVE OPEN, with a source-fidelity blocker for the historical problem statement. Any reported formal-solution metadata must be checked against the exact Ramsey limit and must not be taken to imply its proof. Historic monetary-prize statements do not determine awards.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task proves the recurrence from the monochromatic-neighbourhood argument, verifies \(R(3;2)=6\) using all two-colourings on up to six vertices, and checks the first few factorial recurrence bounds. A separate source task locates the original [Er61] passage and determines whether it concerns Schur numbers or the stated Ramsey limit. Stop before asserting convergence of \(R(3;k)^{1/k}\).

Sources and claim boundaries

No finite exponential-base bound, proof of the limit, protected status change or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1452 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction