Reproduce “SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Zhengyu Li, Curtis Bright, Stefan Trandafir, Adán Cabello, Vijay Ganesh

A SAT-and-NAUTY framework enables certified isomorph-free generation of structured orthogonality graphs while retaining the prefix-pruning guarantees required for orderly search. Applied to extensions of the 25-ray complete Yu–Oh configuration up to 33 rays, the computation found 44 combinatorial candidates, of which only the 33-ray Schütte configuration is realizable in real or complex three-dimensional space.

Key insights

  • RCL preserves the prefix property required by orderly generation while retaining NAUTY’s efficient isomorphism handling. On 1,200 benchmark graphs, its per-graph time stayed near 27 ms, whereas lexicographic checking grew to 3.8 minutes at order 26.
  • Combinatorial KS constraints alone are insufficient: among 44 non-isomorphic 33-vertex candidates, geometric realizability in three-dimensional real or complex space eliminated all but one.
  • The conclusion is deliberately restricted to KS sets containing the complete 25-ray SI-C core; it does not resolve the global minimum-size KS-set problem or classify configurations outside this family.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.