Skip to content

Erdős Problem #87

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

The chromatic number \(\chi(G)\) is the minimum number of colours required to colour a graph's vertices without a monochromatic edge. Its Ramsey number \(R(G)\) is the least integer \(N\) such that every two-colouring of the edges of \(K_N\) contains a monochromatic copy of \(G\).

Erdős #87 asks whether, for every \(\epsilon>0\) and sufficiently large \(k\),

\[ R(G)>(1-\epsilon)^k R(k) \]

holds for every graph \(G\) with \(\chi(G)=k\), where \(R(k)=R(K_k)\). The stronger conjecture asks whether \(R(G)>cR(k)\) for a fixed positive \(c\) independent of \(k\). The order of these quantifiers is important.

A small example

For \(G=K_k\), equality \(R(G)=R(k)\) holds. It does not follow that every graph with chromatic number \(k\) has Ramsey number at least \(R(k)\). Faudree and McKay calculated the pentagonal wheel \(W\) has chromatic number four and \(R(W)=17\), whereas \(R(4)=18\). This refutes an older, stronger conjecture but not the revised large-parameter question.

For fixed \(k=4\), the proposed inequality can tolerate a discrepancy such as \(17/18\); an asymptotic claim is not decided by a single small value.

What is known

Both revised formulations are OPEN. The historical source is Erdős's 1995 problem list cited on Erdős #87, which also records the Faudree–McKay finite result and Wigderson's observation that a probabilistic red-blue colouring yields \(R(G)\gg2^{k/2}\) when \(\chi(G)=k\).

Because the standard diagonal bound gives \(R(k)\le4^k\), the displayed exponential comparison is automatic if \(\epsilon\ge3/4\). This does not address the interesting arbitrarily small positive \(\epsilon\) regime. The exact wheel computation and the original Erdős 1995 printed statement have not been independently page-checked here.

GCL's current state

The pinned catalogue and maintained page (January 2026) classify this problem OPEN. The original source assignment is #1356. This article distinguishes the failed strict inequality \(R(G)\ge R(k)\) from both open weakened versions, without promoting secondary bibliographic remarks to independent source-proof certification.

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 verification task is to encode the small pentagonal-wheel example as a two-colour Ramsey SAT problem. Acceptance requires a two-colouring of \(K_{16}\) without a monochromatic wheel, a complete certificate that every two-colouring of \(K_{17}\) contains one, and a check that the wheel is four-chromatic. Stop at \(k=4\) and make no inference about large \(k\).

Sources and claim boundaries

No new Ramsey bound, independently verified 1993 computation, or editorial admission is claimed.

Catalogue and evidence provenance

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