Skip to content

Erdős Problem #118

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: set 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

In infinite Ramsey theory, one asks whether colouring every edge of a complete graph red or blue must produce a large monochromatic structure. Erdős and Hajnal considered an ordinal or cardinal \(\alpha\) for which every red-blue colouring of the pairs of \(\alpha\) contains either a red complete graph of order type \(\alpha\) or a blue triangle.

In arrow notation this is

\[ \alpha\longrightarrow(\alpha,3)^2. \]

They conjectured that this property would imply \(\alpha\to(\alpha,m)^2\) for every finite \(m\ge3\): a red copy of order type \(\alpha\) or a blue clique of size \(m\) would always appear.

A small example

The blue-triangle condition forbids one tiny monochromatic pattern. A graph may have no blue triangle yet contain a blue four-cycle; the presence of such a cycle is not the same as a blue \(K_4\). This illustrates why controlling blue triangles gives no obvious control of all larger cliques.

The ordinal \(\omega\) is the order type of the natural numbers. Larger ordinal powers, such as \(\omega^{\omega^2}\), have richer order structures. An infinite subset need not be order-isomorphic to the whole ordinal, so cardinal and ordinal Ramsey statements require careful distinction.

What is known

DISPROVED. Schipperus and Darby independently established counterexamples to the implication, with results published or circulated around 1999–2010. An explicit example recorded in the maintained Erdős #118 is due to Larson:

\[ \alpha=\omega^{\omega^2}, \quad \alpha\to(\alpha,3)^2, \quad \alpha\not\to(\alpha,5)^2. \]

The final failure means there exists a two-colouring with neither a red set of order type \(\alpha\) nor a blue \(K_5\). The claim is not that every two-colouring avoids them.

The UCSD primary historical collection Ordinal Ramsey 1 distinguishes positive Chang/Milner theorems for \(\omega^\omega\) from the higher-ordinal counterexamples of Schipperus, Larson and Darby. Importing a positive theorem for the smaller ordinal \(\omega^\omega\) to \(\omega^{\omega^2}\) would be invalid.

GCL's current state

The pinned catalogue and maintained page, edited January 2026, classify #118 DISPROVED. Original source assignment: #1387. The exact ordinal witness and separate cited historical sources have been checked, but the infinitary forcing/ordinal partition arguments have not been independently reproduced.

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 formal-semantics task is to encode \(\alpha\to(\alpha,3)^2\) and its negation for \((\alpha,5)^2\) as quantified statements about edge colourings and order embeddings. Acceptance: correctly transform \(\alpha\not\to(\alpha,5)^2\) into existence of a counterexample colouring, preserve the order type \(\alpha\), and distinguish a blue \(K_5\) from arbitrary blue five-vertex subgraphs. The cited construction remains an imported result.

Sources and claim boundaries

No independently certified ordinal-colouring construction or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1387 — 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