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
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
- Wigderson, arXiv:2409.05931v2, Theorem 1 and Lemmas 2–4, full two-page primary argument inspected.
- Erdős #79; original issue #1348.
- Original problem: Erdős, Faudree, Rousseau and Schelp, Ramsey size linear graphs, Combin. Probab. Comput. 2 (1993), 389–399.
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.