Skip to content

Erdős Problem #165

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 Ramsey number \(R(3,k)\) is the smallest \(N\) such that every red-blue colouring of \(K_N\) contains either a red triangle or a blue complete graph on \(k\) vertices. Equivalently, every triangle-free graph on at least \(R(3,k)\) vertices has an independent set of size \(k\).

Erdős asked for a sharp asymptotic formula. It is known that \(R(3,k)\) grows on the scale \(k^2/\log k\), but the leading constant is not yet settled:

\[ R(3,k)\sim c\frac{k^2}{\log k}\quad\text{for which constant }c? \]

The goal is to determine the coefficient, not simply the exponent of \(k\).

A small example

The five-cycle \(C_5\) has no triangle and has independence number two. Therefore \(R(3,3)>5\). Classical elementary Ramsey theory also gives \(R(3,3)=6\), consistent with the graph interpretation. A lower-bound construction is a triangle-free graph with unusually small independence number; it gives a counterexample to forcing an independent \(k\) set at that order.

What is known

The precise constant remains OPEN. Kim proved in 1995 that \(R(3,k)\gg k^2/\log k\), originally with a small constant. Shearer's upper analysis and earlier Ajtai–Komlós–Szemerédi work give

\[ R(3,k)\le(1+o(1))\frac{k^2}{\log k}. \]

Bohman–Keevash and Pontiveros–Griffiths–Morris established lower constant \(1/4\). Campos–Jenssen–Michelen–Sahasrabudhe later improved it to \(1/3\), and Hefty–Horn–King–Pfender, Improving \(R(3,k)\) in just two bites, improve it to \(1/2\):

\[ \left(\frac12+o(1)\right)\frac{k^2}{\log k} \le R(3,k) \le(1+o(1))\frac{k^2}{\log k}. \]

The maintained Erdős #165, edited March 2026, identifies one-half as the conjectured actual constant. The 2025 preprint's full probabilistic proof has not been independently reconstructed; the sharp upper constant remains one and is not already one-half.

GCL's current state

The pinned and maintained catalogue classify #165 OPEN. Original issue: #1434. The recent arXiv lower-bound statement was checked against the maintained site and preprint metadata, without claiming proof certification or resolution of the upper gap.

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 graphs on at most seven vertices and verifies \(R(3,3)=6\) by exhaustive red-blue edge colourings. Acceptance: identify the \(C_5\) lower witness, show every six-vertex graph has a triangle or independent triple, and retain the distinction between finite Ramsey certificates and asymptotic constants. A proof-level successor would independently review the 2025 triangle-free process and its coefficient before attempting the remaining upper bound.

Sources and claim boundaries

No new sharp Ramsey asymptotic, independent probabilistic-proof certification or editorial admission is claimed.

Catalogue and evidence provenance

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