Research · Papers · Exact answers in open problems · ML-097
Limits of plain CDCL with cardinality totalizers for Turán numbers ex(n, K_4^(3))
ex(14, K_4^(3)) is undecided; CDCL with totalizers hits an empirical wall above n = 9, while degree-sequence cubing refutes cubes at n = 10
Published 2026-09-06
For everyone
Plain summary
Turán numbers ask for the largest number of 3-way connections a network on n points can hold without forming a complete 4-point cluster (K_4^(3)). Automated logic solvers running standard counting circuits hit a wall on these problems. While size n = 7 finishes in 0.1 seconds, instances at n = 10 and above do not finish, spinning through tens of millions of search steps without an answer. Symmetry rules and vertex-deletion helpers do not fix the stall. The value ex(14, K_4^(3)) remains unknown. Splitting n = 10 into sub-cases by fixing exact point degrees does work, refuting each slice in 1 to 50 seconds with checked proofs.
Result
ex(14, K_4^(3)) remains undecided. Monolithic CDCL search with cardinality totalizers hits an empirical wall for 3-uniform Turán cells above n = 9:
- CDCL with degree-sorting symmetry breaking yields no answer on n = 12 at 136 edges (the satisfiable side), n = 12 at 137 edges, n = 13 at 175 edges, and n = 14 at 221 edges after 12M to 20M conflicts.
- Adding vertex-deletion lemma clauses leaves n = 10 at 76 edges and n = 11 at 103 edges unresolved after 6.6M to 6.8M conflicts.
- Exact degree-sequence cubing partitions the n = 10 cell into 22 cubes, refuting individual cubes in 1 to 50 s with verified DRAT certificates (17 of 22 verified at wrap-up).
Setting and definitions
The Turán number ex(n, K_4^(3)) is the maximum number of 3-edges in a 3-uniform hypergraph on n vertices containing no copy of K_4^(3). Target instances are encoded into propositional satisfiability, using cardinality totalizers for edge-count thresholds, degree-sorting clauses for symmetry breaking, and vertex-deletion lemmas for structural bounding.
Method
Kissat executed the benchmark instances:
- Degree-sorting symmetry breaking on n = 12 at 136 edges, n = 12 at 137 edges, n = 13 at 175 edges, and n = 14 at 221 edges.
- Vertex-deletion lemmas on n = 10 at 76 edges and n = 11 at 103 edges.
- Exact degree-sequence cubing on n = 10 across 22 sub-cases, paired with DRAT certificate verification.
Run records are logged in frontier/turan/runs/*.json, PROGRESS.log, and lane WALL.md.
Discussion
Plain CDCL with cardinality totalizers exhibits a steep runtime cliff: n = 7 completes in 0.1 s, but n = 10 exceeds 700 s, and larger instances stall after tens of millions of conflicts. Neither degree-sorting symmetry breakers nor vertex-deletion lemmas mitigate the conflict explosion.
Exact degree-sequence cubing bypasses this barrier, resolving individual n = 10 sub-cases in 1 to 50 s. Untested alternatives include SAT Modulo Symmetries (SMS) on the incidence graph and Markstrom-style orderly generation.
For everyone — the takeaway
What this means
Standard SAT solvers using counting circuits fail on hypergraph Turán problems beyond n = 9. Symmetries and counting constraints overwhelm monolithic search. Resolving open values like ex(14, K_4^(3)) requires structural decomposition, such as degree-sequence cubing, rather than single-pass SAT solving.
Attribution and prior art
Sources: Turan 1941
Register references
- ML-097
- Receipt: box
frontier/turan/runs/*.json - Receipt:
PROGRESS.log - Receipt: lane
WALL.md
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (5 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.