Skip to content

Erdős Problem #166

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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 off-diagonal Ramsey number \(R(4,k)\) is the least \(N\) such that every graph on \(N\) vertices contains either a complete graph on four vertices or an independent set on \(k\) vertices. Erdős conjectured that it has a cubic lower bound up to polylogarithmic factors, namely that there is some fixed \(C\) with

\[ R(4,k)\gg\frac{k^3}{(\log k)^C}. \]

This asks about growth on the cubic scale, not a precise leading constant. It is unrelated to \(R(C_4,k)\), in which a red four-cycle is forbidden instead of a four-clique.

A small example

The five-cycle is \(K_4\) free and has no independent triple, so it gives \(R(4,3)>5\). A large \(K_4\) free graph with independence number below \(k\) witnesses a lower bound for \(R(4,k)\). Such graphs are the objects constructed by extremal probabilistic or algebraic methods.

What is known

PROVED. Sam Mattheus and Jacques Verstraete, The asymptotics of \(r(4,t)\), 2023, prove

\[ R(4,k)=\Omega\left(\frac{k^3}{\log^4 k}\right). \]

The explicit fourth power of the logarithm meets the original unspecified-polylogarithm conjecture. It is not a claim that \(R(4,k)\sim c k^3/\log^4 k\). Ajtai–Komlós–Szemerédi earlier proved the upper estimate

\[ R(4,k)\ll\frac{k^3}{(\log k)^2}. \]

Thus a gap of roughly \((\log k)^2\) remains between the known bounds. Spencer's prior lower estimate \((k\log k)^{5/2}\) was superseded on the polynomial scale.

GCL's current state

The pinned and maintained Erdős #166 classify it PROVED. Original issue: #1435. The primary 2023 arXiv abstract and logarithmic exponent were inspected, but the finite-geometry construction and proof were not independently reproduced. Historical prize metadata does not imply any award adjudication.

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 purely algebraic implication that the 2023 theorem resolves the original existence of a fixed polylogarithmic exponent, explicitly choosing \(C=4\) and noting that \(C\) does not depend on \(k\). Acceptance: preserve the distinction between clique \(K_4\) and cycle \(C_4\) and correctly compare the \(k^3/(\log k)^4\) lower to the \(k^3/(\log k)^2\) upper. Stop before claiming the exact log exponent or a new construction.

Sources and claim boundaries

No new Ramsey construction, independent proof replay or editorial admission is claimed.

Catalogue and evidence provenance

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