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:
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
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\):
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
- Hefty–Horn–King–Pfender, arXiv:2510.19718, primary \(1/2\) lower coefficient.
- Erdős #165, bound chronology and open leading constant.
- GCL original issue #1434.
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.