Skip to content

Erdős Problem #191

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics, 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 each edge of the complete graph on the integers \(\{2,\ldots,N\}\) red or blue. A subset \(X\) is a monochromatic clique when every edge joining two of its members has one common colour.

Erdős asked whether, for every prescribed constant \(C>0\) and all sufficiently large \(N\), every two-colouring contains a monochromatic clique \(X\) with

\[ \sum_{x\in X}\frac1{\log x}\ge C. \]

The logarithms are natural; the domain starts at two to avoid division by \(\log1=0\). The weight is on vertices, although the colours are on edges.

A small example

For \(X=\{2,3,4\}\), the three edges must all be red or all blue. If just one edge differs in colour, \(X\) is not monochromatic even though two of its three edges agree. Its vertex weight is \(1/\log2+1/\log3+1/\log4\).

The statement is asymptotic in \(N\). A monochromatic clique of logarithmic cardinality drawn entirely from very large labels may still have small reciprocal-logarithm weight.

What is known

PROVED. Rödl (2003) first established that the maximum forced weight tends to infinity as \(N\to\infty\), answering the qualitative question. Conlon, Fox and Sudakov, Two extensions of Ramsey's theorem, Duke Mathematical Journal 162 (2013), 2903–2927, determined the sharp order:

\[ \min_{\text{red-blue colourings}}\ \max_{\text{monochromatic }X} \sum_{x\in X}\frac1{\log x} =\Theta(\log\log\log N). \]

Their Theorem 1.1 supplies the explicit lower bound \(2^{-8}\log\log\log N\) for sufficiently large \(N\). Rödl's colouring gives the matching-order upper bound. The same source shows the corresponding universal claim fails for three edge colours: a 3-colouring can keep these weights uniformly bounded.

The maintained Erdős #191 classifies it PROVED. A two-colour result must not be transferred to three colours, and the upper construction must not be misreported as a lower bound.

GCL's current state

Pinned and maintained status: PROVED. Original issue: #1460. The primary 2013 theorem statement and logarithmic order were checked, but its proof and any externally reported Lean formalization have not been independently reconstructed.

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 enumerates all two-colourings of the edges of \(K_N\) for \(N\le6\), calculates the maximum reciprocal-logarithm vertex weight over monochromatic cliques, and computes the minimum over colourings. Acceptance: check every pairwise edge of each clique and compute weights from labels rather than clique size alone. Stop at finite numerical fixtures; no proof of the iterated-logarithm asymptotic follows from enumeration.

Sources and claim boundaries

No new weighted Ramsey theorem, independent formal certification or editorial admission is claimed.

Catalogue and evidence provenance

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