Skip to content

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

\[ R(k)>C^k \]

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

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.

Back to catalogue · Compendium introduction