{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-06","reactions":{},"formalized":true,"formalizes":[{"title":"A new upper bound for error-correcting codes","identifier":"https://doi.org/10.1109/TIT.1962.1057714","relationship":"formalizes"}]}