Skip to content

Erdős Problem #79

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

Two-colour Ramsey theory asks how large a complete graph must be before any red-blue colouring forces either a red copy of a fixed graph \(G\) or a blue copy of another graph \(H\). Write this number \(r(G,H)\).

We call \(G\) Ramsey size-linear if there is a constant \(C_G\) such that

\[ r(G,H)\le C_G e(H) \]

for every graph \(H\) without isolated vertices. Erdős #79 asks whether infinitely many graphs fail this property even though every proper subgraph has it.

A small example

\(K_3\) is Ramsey size-linear: Sidorenko's theorem gives \(r(K_3,H)\le 2e(H)+1\) for graphs \(H\) without isolated vertices. By contrast, \(K_4\) is not Ramsey size-linear. In fact every proper subgraph of \(K_4\) is Ramsey size-linear. The original question asks for infinitely many such minimal obstructions, rather than a second isolated example.

A tree is Ramsey size-linear. Indeed, every graph \(H\) without isolated vertices embeds in a complete graph on at most \(2e(H)\) vertices. Applying Chvátal's exact tree-versus-complete-graph Ramsey formula bounds \(r(T,H)\) linearly in \(e(H)\).

What is known

PROVED. Yuval Wigderson's paper Infinitely many minimally non-Ramsey size-linear graphs, revised 5 May 2025, establishes exactly this assertion in Theorem 1. Its proof is short and directly inspectable.

The three crucial inputs are: every forest is size-linear (Lemma 2); every graph with \(e(G)\ge2v(G)-2\) is not size-linear (Lemma 3); and graphs of arbitrarily large girth with average degree at least four exist (Lemma 4). If there were finitely many minimal obstructions, select a high-girth graph avoiding all their cycle lengths. Its average degree forces non-size-linearity, so an inclusion-minimal non-size-linear subgraph gives a new obstruction, contradiction.

Wigderson explicitly emphasizes that this is a nonconstructive proof. Identifying a concrete new minimal obstruction other than \(K_4\) is still an open successor question, not the original assertion.

GCL's current state

GCL inspected Theorem 1, Lemmas 2–4, and the proof on the 2025 author-hosted arXiv HTML. The original task is #1348. The pinned catalogue says PROVED. The paper's core contradiction is source-checked; its externally cited Ramsey bounds and high-girth constructions are not independently reproved or formalized.

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 proof-replay task is to formalize the minimal-obstruction contradiction assuming three explicit lemmas, with a parameter \(g\) greater than every forbidden cycle length. Acceptance: prove the resulting graph cannot contain any member of a finite obstruction list and still contains a new inclusion-minimal non-size-linear subgraph. Reject arguments that assume a computable minimal-obstruction classifier, or claim an explicit example, which the paper does not provide.

Sources and claim boundaries

No new proof, explicit new obstruction, independent Lean check, or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1348 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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