Erdős Problem #159
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
For two graphs \(H_1,H_2\), their Ramsey number \(R(H_1,H_2)\) is the smallest integer \(N\) such that every red-blue colouring of all edges of \(K_N\) gives a red copy of \(H_1\) or a blue copy of \(H_2\).
Erdős #159 asks whether there exists an absolute constant \(c>0\) such that
The first forbidden graph is the four-cycle \(C_4\), not the complete graph \(K_4\). A logarithmic saving such as \(O(n^2/(\log n)^2)\) is not a positive-power saving \(O(n^{2-c})\).
A small example
In a red-blue colouring of \(K_N\), the red graph avoids \(C_4\) precisely when no two distinct vertices have two different common red neighbours. In that situation, the blue graph is the complement of the red graph. A blue \(K_n\) is an independent set of size \(n\) in the red graph.
This rewrites \(R(C_4,K_n)\) as a graph extremal question: how many vertices can a \(C_4\) free graph have while its independence number is less than \(n\)? The reformulation is elementary but does not supply the required exponent.
What is known
The conjectured power saving remains OPEN. As recorded in the maintained Erdős #159, the classical estimates are
The lower bound is attributed to Joel Spencer [Sp77], and the upper to Endre Szemerédi, cited in the 1978 paper by Erdős, Faudree, Rousseau and Schelp [EFRS78]. Both are source-attributed established estimates. The logarithms leave a gap between a lower power near \(3/2\) and an upper power near two.
The original 1978 problem carried a historical prize of USD 100. That historical prize metadata does not imply any award status, new research campaign authorization or permission to replace the protected source statement. The current catalogue expressly labels the question OPEN.
GCL's current state
The pinned registry has status OPEN; the source issue is #1428. Its protected triage says FORMAL_SOURCE_REFRESH_REQUIRED, because no statement file is in the admitted formal-provider snapshot. This is a source-capture obligation, not proof of or obstacle to the editorial exposition. The original [EFRS78] and [Sp77] pages have not been independently proof-audited here.
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 formalizes the equivalence between red \(C_4\) free or blue \(K_n\) free colourings and graphs without a \(C_4\) with independence number less than \(n\). Acceptance: exhaustive enumeration for \(N\le5\) agrees under both formulations and explicitly distinguishes \(C_4\) from \(K_4\). A separate source task compares original [Er78] and [EFRS78] citations and creates an exact formal statement candidate, with no protected-source override. Stop before claiming a new power-saving estimate.
Sources and claim boundaries
- Erdős #159, original [Er78], [EFRS78] and Spencer [Sp77] bounds.
- GCL issue #1428 and its formal-source-refresh prerequisite.
No proof of a positive exponent saving, new prize determination or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1428 — 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.