The Johnson bound for the independence number of the Johnson graph
Source: github.com/karlesmarin/johnson-bound-palomar/tree/6eb8dad56…
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-06-000013
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-06-000013/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-06-000013/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'