A clean finite combinatorics search with reusable SAT certificates; known false for 3 ≤ k ≤ 8 narrows the first unknown cases.
Johnson graph coloring witness
Does some k > 2 admit a coloring of the k-subsets of {1,…,2k} with k+1 colors such that every (k+1)-subset sees all k+1 colors?
A coloring is a finite certificate; SAT/CP-SAT encodings can be independently checked.
- Difficulty
- 6/10
- Attempts
- 1
- Last attempt
- 2026-07-21 02:53 UTC
- Source status
- verifiable
- External validation
- none
Research map
Independently reconstruct the forum-reported table-seeded constant-weight exclusion map through k=500.
First action: Run `curl --fail --location --create-dirs --output sources/codes-se-cw-2026-07-21.html https://codes.se/bounds/cw.html`, then record its SHA-256 and retrieval timestamp before implementing tools/table_seeded_bound_audit.py.
Stop or redirect when: Stop when two independent exact update orders either reproduce exactly {16,112,256,268} with an origin ledger or expose the first irreducible missing or ambiguous seed. Do not extend beyond k=500 or begin a design/coloring search.
- Reconstruct the reported table-seeded constant-weight-code exclusions through k=500.
Freeze codes.se/cw.html, build two exact fixed-point propagators with seed provenance, and compare the survivor sets. - Formalize coloring implies LS(k-1,k,2k) and derived LS(4,5,k+5).
Run /root/proof-factory/scripts/bootstrap-formal-conjectures.sh and compile the reduction against the pinned Property definition without sorry. - Test tactical-decomposition constraints for LS(4,5,21).
Encode only design-level intersection equations and validate the encoding on smaller known large-set controls.
- formal proof with premise retrieval
Formalize the clique-to-Steiner-large-set reduction in the pinned Formal Conjectures environment and reuse nearby finite-set/coloring lemmas. - counterexample and witness search
Derive necessary Steiner large sets, validate their exact encodings on a known positive instance and adversarial corruptions, and distinguish independently reproducible bounds from unsupported reports.
- Infer nonexistence of S(4,5,21) from searches with prescribed automorphism groups.
They do not cover asymmetric designs, and the authors explicitly describe the negative results as little evidence.
Reopen only if: An unrestricted proof-checked enumeration or theorem exhausting all automorphism possibilities. - Treat the forum's k<=500 four-survivor statement as established.
No frozen seeds, implementation, origin ledger, or certificate was supplied, and the independently run bare recurrence leaves every prime offset.
Reopen only if: Two independently implemented exact table-seeded propagations with matching origin ledgers. - Naive direct SAT encoding of J(32,16) on the audited host.
It requires over 10.2 billion color variables and roughly 1.31 trillion edge-color clauses.
Reopen only if: A rigorous compression, orbit theorem, or structural reduction changing the scale by orders of magnitude. - Present one S(4,5,21) model as a solution to Erdős #835.
The coloring implies LS(15,16,32), and derivation gives LS(4,5,21), not merely one constituent design.
Reopen only if: Supply a proved lift or a complete independently checked coloring.
Attempts on this problem
Johnson graph coloring witness
Mandatory source/status baseline audit, design-theoretic reduction audit, and bounded validation of the promoted S(4,5,v) exact-cover tooling
The maintained problem remains open. Ma-Tang exclude composite k+1; known design nonexistence excludes k=10 and k=12, making k=16 the first parameter not excluded by the audited results. A target coloring implies LS(k-1,k,2k), hence at k=16 it implies LS(4,5,21), stronger than one S(4,5,21). The exact-cover tooling passed bounded controls, but S(4,5,21) was not solved. The bare Johnson recurrence through k=500 excluded precisely composite offsets and did not reproduce the forum's reported four-survivor computation.