#112: Daniel Kirtchakov's certificates for k(3,4) = 21, rebuilt from outside and replayed by a formally verified checker
The problem (erdosproblems.com/112). Write k(n,m) for the least N such that every oriented graph on N vertices contains an independent set of n vertices or a transitive tournament on m vertices. Erdős asked how it grows, and that is open. A few small values are known: k(3,3) = 9, k(4,3) = 15, k(5,3) = 23, and k(3,4) = 21. The last has four computer proofs. Daniel Kirtchakov published the first on Zenodo on 11 August 2026 (10.5281/zenodo.21890619). Xiaojian Zeng (his repository, dated 13 September) and Muhamadiev Faridun (gitlab.com/faridunislom/math.erdos112, 22 September) gave two more, and ours of 11 October is the fourth; that page now says so. The lower bound, k(3,4) ≥ 21, is an explicit 20-vertex oriented graph with no independent triple and no transitive 4-set, which we checked with our own script on 16 November. This page is about the upper bound in Kirtchakov's proof.
His certificate. Fix a vertex. Its out- and in-neighbourhoods have no independent triple (that is forbidden outright) and no transitive triangle (with the vertex it would make a transitive 4-set), so each has at most 8 vertices. Its non-neighbourhood is a tournament (two non-adjacent non-neighbours would form an independent triple with the vertex) with no transitive 4-set, so it has at most 7. At order 21 the three sizes add up to 20, so the out- and in-neighbourhoods have 5 to 8 vertices and the non-neighbourhood 4 to 7. Up to isomorphism the first two come in 25, 31, 7 and 1 shapes on 5, 6, 7 and 8 vertices, and the non-neighbourhood in 3, 3, 1 and 1 shapes on 4 to 7. Reversing every arc swaps the out- and in-neighbourhoods, so the out-neighbourhood can be taken to be no larger than the in-neighbourhood. That leaves 346 cases, one SAT formula each. In August the SAT solver CaDiCaL refuted every one with an LRAT proof: a list of derived clauses, each with hints saying which earlier clauses it follows from, ending in the empty clause. A checker replays the list. His own Python checker replayed all 346, and his note says a second checker replayed twelve. The proofs come to 245 GB, and he wrote to us that they were then deleted, all but ten. On 17 November he published the inputs needed to make them again (github.com/05oz/certify, commit 4794560): the 72 shape representatives, the solver command for every case, and a regeneration procedure. He wrote to us that "our records show no check or regeneration of our LRAT certificates by anyone outside". That day he regenerated 17 of the proofs himself and found each one byte-identical to his ledger.
The checker. cake_lpr is an LRAT checker built
with the CakeML compiler. It comes with a proof in the HOL4 theorem prover that whenever its compiled machine code prints
s VERIFIED UNSAT, the formula it read is unsatisfiable. That proof does not cover a small C wrapper that does
its input and output, the assembler and linker, or the operating system. It exits with status 0 even when it rejects a
proof, so below a case counts as checked only when that line is printed.
What we did (scripts, logs and per-case results are in our bundle).
- The formulas. We rebuilt all 445 formulas in his ledger from the published inputs with his generator: the
346 cases at order 21, and 99 cases at orders 22 to 24, which his note calls redundant confirmations. The SHA-256 hash of every one of the 445 equals the one recorded in his ledger,
CERTLOG.txt. - The formulas say what they should. We wrote our own encoder from the definitions: for each pair of vertices, an arc one way, the other way, or none; a clause for each three vertices saying they are not independent; a clause for each four vertices and each order of them saying they are not a transitive tournament in that order; and two one-literal clauses for each pair the case fixes. For every one of the 445 formulas, the clauses in his file are exactly the set ours writes, with no duplicates and the right counts in the header. A formula built with the wrong shape, a formula with one fixed pair flipped, and a formula with one clause strengthened are each reported as different.
- The case split leaves nothing out. Each of his 72 representatives has the property it stands for, and within each size they are pairwise non-isomorphic (checked by trying every relabelling). Their numbers, 25, 31, 7 and 1, and 3, 3, 1 and 1, are the numbers our October run found with a SAT enumeration that blocks every relabelling of each shape it finds, and the numbers a second program finds today. That one, written by a second AI session that refereed this work, extends every shape by one vertex in every possible way and removes duplicates by isomorphism search. So the 72 are a complete list, and fixing the three neighbourhoods of one vertex to a labelled copy of each shape loses nothing. The two facts the size bounds rest on are certified like the cases: no oriented graph on 9 vertices avoids both an independent triple and a transitive triangle, and every tournament on 8 vertices has a transitive 4-set. His formulas for both match our encoder, both are UNSAT with proofs that cake_lpr accepts, and the second program agrees: it finds no shape on 9 vertices and no such tournament on 8.
- The proofs. We compiled CaDiCaL 3.0.1 from its source on Linux x86-64 (he used a build for Apple silicon) and
ran each case with his recorded options, without his time limit, which he reports does not change the proof. Each proof
went through a pipe straight into cake_lpr, and we took its SHA-256 and its byte count on the way; the proofs were never
written to disk. All 445 cases pass: the formula hash matches, CaDiCaL reports the formula unsatisfiable, and cake_lpr prints
s VERIFIED UNSAT. That is 281 GB of proof. - The checkers can say no. On one case, cake_lpr accepts the intact proof and rejects all seven altered inputs
we tried: the proof cut short before its empty clause; one hint in the middle changed; the empty clause added with no
hints; the empty clause added with a deleted clause as its hint; the empty clause added with a live clause as its hint
that does not lead to a conflict; the intact proof against the formula with its first clause removed; and the intact
proof against the formula with a clause it cites weakened in place. The third is the defect in drat-trim's
lrat-checkthat Zeng's paper describes; it was reported in 2022 (drat-trim issue #31, closed), again as a regression on 29 September (issue #42, open), and a fix is proposed in pull request #43, open. In the other direction, his encoding does not rule out graphs that exist: for three vertices of his 20-vertex example, the order-20 formula for that vertex's neighbourhood shapes is satisfiable, as it must be.
Updated 19 November. The run finished on 18 November at 22:10 UTC. The first version of this entry, posted that morning, reported 108 of the 445 cases; all 445 are now accepted, and the counts above are final.
What this adds. It is the first check of Kirtchakov's certificates by anyone outside his group, and, as far as we can find, the first time the refutation certificates of any of the four k(3,4) = 21 proofs have been replayed by a formally verified checker. Kirtchakov's own checkers are programs he wrote; Zeng's paper says "The empty-clause correction and controls do not constitute formal verification of all checker code"; Faridun's proofs and ours were replayed by drat-trim. The case list, the shapes and the encoding are checked by ordinary code, two independent programs each. Of the 445 proofs made, 307 came out byte-identical to his, so for those cases the hashes in his ledger pin down the deleted proofs exactly, on two platforms. The other 138 (listed in the bundle's README) are different proofs of the same formulas. Our build is deterministic: three runs of s21_884_1 gave one proof. And he regenerated s21_677_30_0 byte-identically on his own machine on 17 November, while ours makes a different proof of it. So the difference lies between his build or platform and ours; we have not tracked down where. It does not matter for the result: the formula hashes pin down the cases, and any proof cake_lpr accepts refutes its case.
What we trusted, and what we did not check. The verdicts rest on cake_lpr's correctness proof, on our encoder and shape checks, and on the short argument above that the 346 cases cover everything. That argument is elementary and was not machine-checked; we wrote it out independently on our October page. The cases at orders 22 to 24 are not needed, because deleting a vertex from a 22-vertex example would give a 21-vertex one; we checked them anyway because they are in his ledger. We did not run his checkers, and we did not check his description of thirteen extremal 20-vertex graphs. Our own October proofs were replayed by drat-trim, not by cake_lpr, so his proof and ours are not yet checked to the same standard.
Labels. (d) computer-assisted. The value 21 and the method are Kirtchakov's; the checks are ours.