Skip to content

Erdős Problem #809

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

chi_S(n,e,H) is the MINIMUM number r of edge colors for which SOME n-vertex graph with e edges admits a coloring in which EVERY copy of H is RAINBOW (all its edges distinct colors). For e=floor(n²/4)+1 and H=C_(2k+1), Erdős asks chi_S~n²/8 for all k>=3.

The original k>=3 conjecture covers odd cycles of length at least seven. The 2026 theorem covers k>=4, namely cycles of length at least nine. The outstanding k=3 case is C7. The known anomalous answers for triangles (k=1) and C5 (k=2) fall outside the original quantifier range.

A small example

A triangle C3 has three edges: to make any triangle rainbow takes at least three colors (if a triangle occurs). For n sufficiently large with e>floor(n²/4), a triangle is guaranteed by Mantel's theorem. Coloring with three colors so that all triangles are rainbow is achievable in suitable n-vertex/e-edge graphs according to cited extremum; verifying existence is distinct from counting triangle edges in isolation.

This finite fixture tests the conventions. It does not certify any of the asymptotic or all-graphs assertions.

What is known

The Bucić–Chen–Ma preprint (2026) explicitly states its theorem for every k>=4; the maintained #809 remains OPEN overall. They prove the asymptotic for every k>=4 (cycle length >=9); k=3 is C7, still not covered. Separately k=1 (C3) chi_S=3, and k=2 (C5) chi_S=floor(n/2)+3 for sufficiently large n by Erdős–Simonovits as reported in [BEGS89]. These smaller k are OUTSIDE original k>=3 quantification. The 2026 paper's abstract was directly checked; its full proof and the older BEGS89 article were not independently replayed. Do not call entire problem proved.

The distinctions between established partial theorems, original open parts, and disproved universal claims have been preserved. Historical publications are attributed, rather than presented as new GCL mathematics.

The stated target, for \(k\geq3\), is

\[ \chi_S\left(n,\left\lfloor n^2/4\right\rfloor+1, C_{2k+1}\right)\sim\frac{n^2}{8}. \]

Bucić–Chen–Ma have proved this for \(k\geq4\). The excluded case \(k=3\) is precisely the seven-cycle. The triangle and five-cycle are indexed by \(k=1,2\) and are outside the original quantifier.

GCL's current state

The original authenticated source-return record has a disposition of STATUS_CONFLICT. This explanatory manuscript is editorially reviewed through protected EC-BULK-005-R4. The substantive k=3 (C7) question remains open, the original STATUS_CONFLICT source report is preserved, and no full theorem proof is certified by GCL. The mathematical status of individual subquestions is not determined by a single registry label.

What remains

Source-lock BCM26 theorem for every k>=4 and precisely identify outstanding k=3. For finite small n, enumerate n-vertex e-edge graphs, colorings, and rainbow C7 when computationally tractable; do not mistake C5 exceptional k=2 as an objection to k>=4 theorem.

Critical editorial review must independently distinguish the covered k>=4 family from the still-open k=3 case; full proof replay remains a distinct mathematical obligation.

Sources and claim boundaries

  • Erdos problem #809 and maintained source and bibliography, retrieved by web search 14 October 2026.
  • Authenticated issue-bound return for #809, preserving source limitations and open proof obligations.
  • Pinned teorth/erdosproblems repository revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, source blob 4e60263a80af6207aca494d2e1388e44fa372889. No protected source lock was silently changed.
  • Editorial acceptance: Protected V2 batch EC-BULK-005-R4, exact-hash bound. Source publication: protected merge completed. Public mathematical rendering: verified before admission. New theorem certification: NONE.

Catalogue and evidence provenance

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