Id: palomar/PALOMAR-2026-11-06-000013 Url: https://github.com/karlesmarin/johnson-bound-palomar/tree/6eb8dad56bc31d0e5b0b64ad0931281bcbd71703 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-06-000013-v1.json Repo: https://github.com/karlesmarin/johnson-bound-palomar Tags: math.CO, msc:05C69, msc:94B65 Score: 0 Title: The Johnson bound for the independence number of the Johnson graph Trust: high Domain: math.CO Source: palomar Authors: Carles Marín Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-06 Formalized: true Formalizes: title=A new upper bound for error-correcting codes identifier=https://doi.org/10.1109/TIT.1962.1057714 relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-06-000013 The Johnson graph J(n, k) has the k-subsets of an n-set as vertices, two of them adjacent when they share k - 1 elements; an independent set is a constant-weight binary code of length n, weight k and minimum distance 4. This Lean 4 formalization proves Johnson's 1962 bound α(J(n, k)) ≤ johnsonBound n 4 k, where johnsonBound is the recursive bound A(n, d, w) ≤ ⌊n/w · A(n - 1, d, w - 1)⌋, as stated in google-deepmind/formal-conjectures (Erdős Problem 835), where it is a solved statement left without proof. The proof is by recursion on (n, k): double counting the pairs (point, member) and…