Skip to content

Erdős Problem #812

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

Let R(n)=R(n,n) denote the 2-colour diagonal Ramsey number. Are there constants c>0 and n0 with R(n+1)/R(n)>=1+c for all n>=n0? Separately, is R(n+1)-R(n)>>n²? Both original questions remain OPEN; do not confuse them with bounds for a two-step increment.

A small example

Known small values R(2)=2, R(3)=6, R(4)=18 give increments 4 and 12, both satisfying the linear 4n-8 lower bound. Finite values do not establish eventual multiplicative separation. Preserve n>=2 for displayed BEFS estimate.

What is known

Maintained https://www.erdosproblems.com/latex/812, read 2026-10-14: Burr–Erdős–Faudree–Schelp [BEFS89] prove R(n+1)-R(n)>=4n-8 for every n>=2. A separate lower bound from Erdős problem #165 implies R(n+2)-R(n)>>n^(2-o(1)). This two-step estimate does NOT establish one-step n² or a uniform multiplicative gap. Full 1989 and #165 primary proof not independently replayed.

The quoted 1989 lower bound is \(R(n+1)-R(n)\geq4n-8\) for \(n\geq2\). The sharper two-step estimate is of the form \(R(n+2)-R(n)\gg n^{2-o(1)}\). Since a two-step difference is the SUM of two consecutive increments, this does not give a quadratic bound for each individual increment. The multiplicative ratio conjecture is stronger still.

The established single-step result and reported two-step consequence are different assertions:

$$

R(n+1)-R(n)\geq 4n-8\quad(n\geq2),

$$

$$

R(n+2)-R(n)\gg n^{2-o(1)}.

$$

Writing the latter as the sum of two adjacent single-step gaps shows why it cannot settle both individual gaps, much less the proposed ratio separation.

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: open diagonal ramsey one step vs two step gap. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Source-lock [BEFS89] theorem and the precise #165 two-step bound, including implicit constants and o(1) quantifiers. Implement finite graph two-colour Ramsey checker for R(3)=6 or use exact known values as bounded fixture. Keep one-step and two-step claims separate.

Critical review must independently verify the original primary theorem, hypotheses, quantitative constants and simple examples. Passing source tests does not establish publication or mathematical proof certification.

Sources and claim boundaries

  • Erdős problem #812, maintained LaTeX and original authenticated source return, checked 14 October 2026.
  • Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The source comment contains original bibliography and limits of direct proof inspection.
  • Editorial acceptance: NONE. Protected merge: NONE. Real-browser MathJax: NOT VERIFIED. Lean/new theorem certification: NOT CLAIMED.

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2083 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned 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