Erdős·erdos:809
Erdős 809
No independent check recorded yet. A formal artifact, declaration or published object is attached, but no rebuild of it is recorded here.
A Palomar registration names this problem. It is shown below but not counted as a check of the claim.
Fidelity F2: The correspondence is declared through an alignment table and written divergences.
graph theory, ramsey theory·Source
AI activity
How grades workNo AI contribution recorded against this statement.
Claimed on erdosproblems.com
2Proof claims posted on erdosproblems.com, which says that listing a claim “is no guarantee of proof correctness”. The register records who claims what, with which systems, and links to each claim there. Nobody has examined them, and none counts in the register's totals.
Fidelity
How fidelity is gradedF2 declared. The correspondence is declared through an alignment table and written divergences.
Checks
2-
verified·Palomar
Registered by Palomar at 15f8839e: Comparator confirmed 1 theorems prove the recorded statement within Palomar's axiom policy, replayed through Lean's kernel and the independent nanoda kernel. The project names this problem, which does not establish that it proves the result claimed here, so it is not counted as a check of it
-
verified·Palomar
Registered by Palomar at 0f27743f: Comparator confirmed 1 theorems prove the recorded statement within Palomar's axiom policy, replayed through Lean's kernel and the independent nanoda kernel. The project names this problem, which does not establish that it proves the result claimed here, so it is not counted as a check of it
Declared by the projects
2As each project's formalization.yaml states it.
Erdős Problem 809: an independent proof of the seven-cycle threshold
- authors
- Asad Shahab
- method
- agent — Aristotle, Claude, GPT-6 Astra
- review
- self-assessed
- axioms
- Classical.choice, Quot.sound, propext
- sorry
- 0 unproved goals declared
- sources
- The Burr-Erdős-Graham-Sós conjecture for the seven-cycle — formalizes; On a maximal anti-Ramsey conjecture of Burr, Erdős, Graham, and Sós — formalizes; Maximal antiramsey graphs and the strong chromatic number — background; Erdős Problem 809 — background
- related
- PALOMAR-2026-09-30-000004 — independent; Asad-Shahab/erdos-809/tree/d7fcc0cd633946076a0ccc965fc088fa2cca676f — builds-on
- divergences
- No intended change to the extremal statement. The Lean proof extracts a triangular matching from exact covers, and its upper construction uses an epsilon-dependent linear imbalance between two cliques; Section 10.2 of the paper explains these exposition differences. The Palomar statement expands the original definitions into Mathlib primitives. No extra mathematical hypothesis is added.
- checked by
- Palomar
Erdős Problem 809: rainbow odd cycles
- authors
- Jacob Parish
- method
- agent — gpt-6-sol
- review
- self-assessed
- axioms
- Classical.choice, Quot.sound, propext
- sorry
- 0 unproved goals declared
- sources
- Maximal antiramsey graphs and the strong chromatic number — formalizes; On a maximal anti-Ramsey conjecture of Burr, Erdős, Graham, and Sós — formalizes; Erdős Problem #809 — background
- divergences
- No known divergence in the main result's mathematical content from the cited odd-cycle threshold conjecture. The Lean statement uses graphs with at least floor(n²/4) + 1 edges; deleting edges gives the equivalent exact-edge formulation.
- checked by
- Palomar
Follow and discuss
All discussionFollow this problem
An email when it has a new claim, check, bounty or discussion. You confirm once and can stop with one click.
Discussion and bounties for this problem load here.
Seen recently
What the monitors picked up in the last thirty days, not yet graded.
Something wrong or missing here? Request a correction or add a claim, with its sources.
Claims and corrections from readers
All of themFormal material
Formal statements · 0
No formal statement located.
Cited proofs · 0
No proof artifact cited by the formal record.
Also known as · 1
- https://www.erdosproblems.com/809
Cite this record
qed.bot, “Erdős 809”, https://qed.bot/s/erdos-809, as of 20 Nov 2026.