Erdős Problem #78
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
A Ramsey graph is a graph with neither a large clique nor a large independent set. Erdős #78 asks for a constructive, rather than merely probabilistic, proof that the diagonal Ramsey number satisfies
for some fixed constant \(C>1\) and all sufficiently large \(k\). Here \(R(k)\) is the least number of vertices forcing a monochromatic \(K_k\) in every two-edge-colouring of the complete graph. Finding a graph with no clique or independent set of order \(k\) shows \(R(k)\) exceeds its vertex count.
A small example
Color the five-cycle's edges red and its complement blue. Both red and blue graphs are \(C_5\), so neither contains a triangle and \(R(3)>5\). This explicit finite witness has no bearing on the required uniform exponential family.
For a graph on \(N\) vertices with both clique number and independence number below \(k\), one must exhibit a single algorithm that constructs the graph for arbitrarily large \(k\) while keeping \(N>C^k\). A family whose forbidden homogeneous size is merely \(N^{0.01}\) does not suffice: \(N^{0.01}\) grows much faster than \(\log N\).
What is known
The problem remains OPEN in its stated constructive exponential form. Erdős's probabilistic argument gives \(R(k)\gg k2^{k/2}\), but sampling a random graph and showing that a suitable outcome exists does not supply the intended deterministic, efficient construction.
Gil Cohen's primary paper Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs constructs explicit Ramsey graphs with no homogeneous set of order \(2^{(\log\log N)^c}\) for a universal \(c>0\). The maintained problem page records an improvement by Li to a polylogarithmic bound \((\log N)^C\). Both are major advances but fall short of controlling the largest homogeneous set by a constant multiple of \(\log N\).
GCL's current state
The original source assignment is #1347. The pinned 2025 catalogue and the maintained page (edited 23 January 2026) classify the problem OPEN. Cohen's published primary abstract was inspected; Li's exact primary theorem and construction remain a separate source audit. No proof of the constructive exponential Ramsey lower bound is claimed.
An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.
What remains
A bounded task is to formalize the equivalence between a deterministic \(N\) vertex graph with \(\omega(G),\alpha(G)<k\) and the lower bound \(R(k)>N\). Acceptance: an exact finite checker verifies the five-cycle witness and the order of quantifiers for a proposed graph-construction algorithm. Falsification: any monochromatic \(K_k\), inappropriate dependence of the construction on a random oracle, or only polynomially small homogeneous sets. Stop before claiming any new exponential family.
Sources and claim boundaries
- Cohen, Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs, SIAM J. Comput., published primary abstract inspected.
- Erdős #78, including historical references and the 2023 Li lead.
- GCL original source issue #1347; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
No construction meeting the requested exponential bound, new theorem, Lean certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1347 — 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.