Erdős Problem #810
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
Does there exist epsilon>0 and for EVERY sufficiently large n a graph G on n vertices with >=epsilon*n² edges whose edges use at most n colors such that every copy of C4 has four different edge colors? The anti-Ramsey minimum chi_S(n,e,C4) is the related quantity.
A four-cycle being rainbow means that its four edges have four different colors. Requiring this in a graph with quadratically many edges while using at most n colors is substantially stronger than coloring a single isolated four-cycle. The link to forbidden configurations in three-uniform hypergraphs is an additional open obstacle, not a solution.
A small example
The graph C4 alone on n=4 vertices has 4 edges colored with four DISTINCT colors: its one four-cycle is rainbow. This is a finite construction only, no uniform absolute density for arbitrarily large n. If a host graph has no C4 at all the coloring condition is vacuous, but it cannot be naively equated with dense existence.
This finite fixture tests the conventions. It does not certify any of the asymptotic or all-graphs assertions.
What is known
Maintained #810 OPEN. Burr–Erdős–Graham–Sós [BEGS89] expect NO, and prove negative analogue when C4 is replaced by P4. Sárközy–Selkow [SaSe06] prove strong r/n->infinity for connected bipartite G other than a star EXCEPT complete bipartite graphs, leaving C4=K2,2 open. A weaker construction from 3-uniform (7,4)-free hypergraphs has e~g(n;7,4); g(n;7,4)=o(n²) itself unresolved [1178]. Original proofs not fully inspected.
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.
Equivalently, in the anti-Ramsey notation, the question seeks a fixed \(\varepsilon>0\) such that for all large \(n\),
$$
\chi_S(n,\lceil\varepsilon n^2\rceil,C_4)\leq n.
$$
The ceiling simply enforces an integer edge count; care is needed about monotonicity in the exact original definition of \(\chi_S\). The known general bipartite theorems leave \(K_{2,2}=C_4\) as an exception.
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 dense c4 rainbow with n colors. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
Build explicit 4-cycle enumerator with color uniqueness and a C4-only positive fixture plus nonrainbow negative fixture; inspect 1989, 2006 originals and separate infinitely many n from all sufficiently large n.
Before protected admission the responsible editor must inspect full original proofs where not yet read, verify the executable finite example and mathematical notation, test actual public rendering, and record a critical review disposition. Local gate success alone is insufficient.
Sources and claim boundaries
- Erdos problem #810 and maintained source and bibliography, retrieved by web search 14 October 2026.
- Authenticated issue-bound return for #810, preserving source limitations and open proof obligations.
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: #2081 — 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.