Skip to content

Erdős Problem #129

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 a complete graph \(K_N\) with one of \(r\) colours. Define \(R(n;k,r)\) as the least \(N\) such that every such colouring has an \(n\) vertex subset on which at least one colour contains no complete graph \(K_k\).

Erdős and Gyárfás asked, as currently printed, whether for fixed \(r\) there is \(C(r)>1\) with

\[ R(n;3,r)<C(r)^{\sqrt n} \]

for all sufficiently large \(n\). Beware: this is not the usual multicolour Ramsey number asking for a monochromatic clique; it asks for a large subset omitting a monochromatic triangle of some colour.

A small example

When \(r=2\) and \(k=3\), a subset qualifies if it has no red triangle or no blue triangle. A colouring in which every \(n\) vertex subset contains both a red and a blue triangle is therefore a counterexample at that \(N\). It is not enough to find one monochromatic triangle somewhere in the graph.

For a random red-blue edge colouring, a prescribed triangle is monochromatic red with probability \(1/8\), independently of other edge-disjoint triangles. The complement event of having no red triangle can thus be bounded using a collection of many such triangles.

What is known

THE LITERAL PRINTED CONJECTURE IS DISPROVED; THE INTENDED HISTORICAL PROBLEM IS UNCLEAR. Antonio Girão observed, as recorded on Erdős #129, that already

\[ R(n;3,2)\ge c^n \]

for an absolute \(c>1\). To see the mechanism, any complete graph on \(n\) vertices contains a constant times \(n^2\) edge-disjoint triangles: remove edges of triangles greedily until the remainder is triangle-free and apply Mantel's bound. In a random two-colouring, the chance that a given \(n\) subset has no red triangle or no blue triangle is at most \(2(7/8)^{\Omega(n^2)}\). There are at most \(N^n\) such subsets. For \(N=\lfloor e^{cn}\rfloor\) and sufficiently small \(c>0\), the union bound is less than one, showing a colouring with no qualifying subset.

This exponential lower bound contradicts every \(C^{\sqrt n}\) upper bound for \(r=2\). However, Erdős and Gyárfás reportedly claimed a substantially different lower growth estimate in their original presentation. The maintained site therefore retains an OPEN/AMBIGUOUS classification pending recovery of what formulation was originally intended. We should not assert that an unknown corrected question is solved.

GCL's current state

The pinned 2025 entry and original issue #1398 say OPEN. The maintained page explicitly documents Girão's refutation of the statement as written and warns that the original question may be misstated. The exact original Erdős 1997 publication has not been page-audited here; this status drift is recorded as a source discrepancy.

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 successor should write a formal union-bound proof with explicit constants: construct at least \(n^2/20\) edge-disjoint triangles in \(K_n\) for sufficiently large \(n\), count bad \(n\) subsets and choose a fixed exponential base. Acceptance: independently verify triangle edge-disjointness, the probability bound, and the order of quantifiers. A separate source task must locate the original [Er97b] problem wording. Stop short of assigning a new status to a conjecture whose intended definition is unresolved.

Sources and claim boundaries

The printed upper bound is mathematically false; the historical intended conjecture is unadjudicated. No new research claim or editorial admission is asserted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1398 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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