Skip to content

Erdős Problem #77

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

Imagine coloring every connection between \(n\) people red or blue. How large must \(n\) be to guarantee a group of \(k\) people all of whose mutual connections have one color? The smallest such \(n\) is the diagonal Ramsey number \(R(k,k)\), written \(R(k)\) in Erdős #77.

The question asks whether the exponential growth rate stabilizes:

\[ \lim_{k\to\infty}R(k)^{1/k}. \]

Taking the \(k\) th root removes the dominant exponential scale. Even the existence of this limit remains open. An upper bound and a lower bound do not imply convergence.

A small example

The smallest nontrivial case is \(R(3)=6\). Given a red-blue coloring of the \(15\) edges of \(K_6\), choose a vertex: at least three of its five incident edges share a color. If an edge joining two of those three neighbors has that same color, it closes a monochromatic triangle. Otherwise all three edges among the neighbors have the opposite color, also giving a monochromatic triangle.

Five vertices do not suffice: color the edges of a \(5\)‑cycle red and its five complementary edges blue. Both color classes form \(5\)‑cycles, so neither contains a triangle. This elementary calculation concerns \(k=3\), not the limiting root.

What is known

The classical probabilistic lower bound yields

\[ \sqrt2\le\liminf_{k\to\infty}R(k)^{1/k}. \]

An elementary recurrence formerly gave the upper bound \(4\) for the limsup. Campos, Griffiths, Morris and Sahasrabudhe broke this decades-old barrier. Gupta, Ndiaye, Norin and Wei sharpened the exponential bound; their 2024 primary preprint explicitly proves

\[ R(k,k)\le 3.8^{\,k+o(k)}. \]

The maintained problem page records a refined numerical constant of approximately \(3.7992\) from this optimization. To avoid overstating what was checked directly in the primary abstract, the conservative value \(3.8\) is used for the rigorous interface here. Therefore

\[ \sqrt2\le\liminf R(k)^{1/k} \le\limsup R(k)^{1/k}\le3.8. \]

These inequalities leave both existence and value of the limit unresolved.

GCL's current state

The canonical source classifies #77 OPEN. GCL examined the original assignment, the maintained historical note, the 2024 primary abstract and the exact finite \(R(3)=6\) argument. This is a pending local exposition, not a novel Ramsey bound. Original assignment #1346 now has authenticated source evidence, but not editorial admission.

The original GitHub issue now contains the authenticated RESULT/1 source report. This does not imply independent mathematical review or editorial admission.

What remains

A bounded computational successor is to enumerate all red-blue colorings of \(K_5\) and \(K_6\), independently classify those containing monochromatic triangles, and certify \(R(3)=6\) with exact combinatorial witnesses. A separate analytic exercise proves that if \(R(k)\le C^{k+o(k)}\), then \(\limsup R(k)^{1/k}\le C\); it must not claim existence of the root limit. Source auditing should pin the exact optimization version before quoting the refined decimal constant.

Sources and claim boundaries

The finite calculation does not settle the open asymptotic question. No new bound, certification or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1346 — 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