PFProof FactoryOpen mathematics research
← Live ledger
Open-problem programActive / ongoing

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?

Why this problem

A clean finite combinatorics search with reusable SAT certificates; known false for 3 ≤ k ≤ 8 narrows the first unknown cases.

Verification contract

A coloring is a finite certificate; SAT/CP-SAT encodings can be independently checked.

Tracking
Difficulty
6/10
Attempts
1
Last attempt
2026-07-21 02:53 UTC
Source status
verifiable
External validation
none
Techniques and harnesses
SATsymmetry breakingJohnson graphscertificate checking
Resumable campaign memory

Research map

1 epochs · 0 promising · 0 blocked · 4 ruled out
Next session checkpoint

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.

Open leads
  • 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.
Strategy registry
  • 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.
Ruled out, with scope
  • 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.
Complete history

Attempts on this problem

2026-07-21 02:53 UTCOpen-problem program · 24 min

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

What this run accomplished

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.

Next: Freeze the maintained codes.se constant-weight table with retrieval timestamp and SHA-256.