Erdős·erdos:835
Erdős Problem 835
Machine-checked by Palomar.
Fidelity F3: The project checks its proof with Comparator against a statement from the Erdős collection of a corpus written separately from the proof, and held here.
graph theory, hypergraphs·Source
AI activity
How grades workLikely folklore
Reasoning and sources
Autonomy
Secondary contribution: formalization
Details
proof to formalize: Likely folklore
Sources
Fidelity
How fidelity is gradedF3 anchored. The project checks its proof with Comparator against a statement from the Erdős collection of a corpus written separately from the proof, and held here.
Checks
2-
verified·Palomar
Registered by Palomar at 6eb8dad5: Comparator confirmed 1 theorems prove the recorded statement within Palomar's axiom policy, replayed through Lean's kernel and the independent nanoda kernel
-
verified·Palomar
Registered by Palomar at 3a8d4cb3: Comparator confirmed 4 theorems prove the recorded statement within Palomar's axiom policy, replayed through Lean's kernel and the independent nanoda kernel
Declared by the projects
2As each project's formalization.yaml states it.
The Johnson bound for the independence number of the Johnson graph
- authors
- Carles Marín
- method
- agent — Claude (Anthropic)
- review
- unchecked
- axioms
- Classical.choice, Quot.sound, propext
- sorry
- 0 unproved goals declared
- results
- 1 main results named, checked with Comparator, with an alignment table
- sources
- A new upper bound for error-correcting codes — formalizes, authors n/a; Erdős Problem #835 — background, authors n/a
- related
- google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/835.lean — builds-on; karlesmarin/formalizations/blob/e9efea0b09824a4f9c7a2a4c7058288c5eb0bfd4/Formalizations/Combinatorics/SimpleGraph/JohnsonBound.lean — other
- divergences
- None in content. The statement is a theorem here and a lemma in formal-conjectures; definitions and notation are identical.
- checked by
- Palomar
Erdős Problem 835 when k + 1 is composite: the chromatic number of J(2k, k) exceeds k + 1
- authors
- Matt Stokes
- method
- agent — Claude (Anthropic)
- review
- unchecked
- axioms
- Classical.choice, Quot.sound, propext
- sorry
- 0 unproved goals declared
- results
- 4 main results named, checked with Comparator, with an alignment table
- sources
- A note on Erdős Problem #835 — formalizes, authors not-contacted; Erdős Problem #835 — background, authors n/a
- related
- google-deepmind/formal-conjectures/blob/5a2fb85045c86e4a184b15ce7531ba199a3c4580/FormalConjectures/ErdosProblems/835.lean — builds-on; stokes/erdos835-lean/tree/daee0bc82ad2a1c640b81bd967a77bbbe208d4a2 — other
- divergences
- None in content. Relative to formal-conjectures, the namespace is Erdos835Palomar and Composite (k + 1) replaces (k + 1).Composite. Relative to Ma and Tang, the vertices of J(n, k) are k-element Finsets of Fin n (subtype), the chromatic number is Mathlib's SimpleGraph.chromaticNumber in ℕ∞, and the colouring property is stated for Fin (2 * k).
- 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 · 1
Recorded elsewhere
Compare the registriesAlso known as · 3
- https://www.erdosproblems.com/835
- https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/835.lean
- FormalConjectures/ErdosProblems/835.lean
Cite this record
qed.bot, “Erdős Problem 835”, https://qed.bot/s/erdos-835, as of 20 Nov 2026.