qedbot

Erdős·erdos:835

Erdős Problem 835

conjecture formal record: mixed source: verifiable F3 anchored

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 work
AlphaProof

26 Dec 2025·supporting task

Likely folklore

partial A1 V1
Reasoning and sources

Autonomy

Secondary contribution: formalization

Details

proof to formalize: Likely folklore

F3 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.

Anchored to google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/835.lean

declares divergences from its source a thin wrapper around another repository not reviewed

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

    project registered at a pinned commit·2026-11-06·commit 6eb8dad56bc3

    PALOMAR-2026-11-06-000013

  • 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

    project registered at a pinned commit·2026-11-01·commit 3a8d4cb34820

    PALOMAR-2026-11-01-000008

Declared by the projects

2

As each project's formalization.yaml states it.

The Johnson bound for the independence number of the Johnson graphkarlesmarin/johnson-bound-palomar · joined by anchor · Palomar

Read formalization.yaml

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
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 + 1stokes/erdos835-palomar · joined by anchor · Palomar

Read formalization.yaml

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
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 discussion

Discussion and bounties for this problem load here.

Something wrong or missing here? Request a correction or add a claim, with its sources.

Formal material

Formal statements · 1
Cited proofs · 2

Recorded elsewhere

Compare the registries
  • palomar — The Johnson bound for the independence number of the Johnson graph

    checked·their labels: registered

  • palomar — Erdős Problem 835 when k + 1 is composite: the chromatic number of J(2k, k) exceeds k + 1

    checked·their labels: registered

Also 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.

This record as plain text, with each claim, its grades and its sources.