Erdős Problem a Daythe open tracker
ERDŐS #112 · READER SUBMISSION

An exposition of a known result

VERIFIED2026-11-16 · Daniel Kirtchakov (Half Ounce Research)
Community database OPENas of 2025-08-31tags graph theory, ramsey theoryproblem page · erdosproblems.com/112
Our review · 2026-11-16

Verdict: VERIFIED. The priority note is right. Daniel Kirtchakov published k(3,4) = 21 on Zenodo on 11 August 2026, two months before our page of 11 October, and that page's sentence "We found no publication of the value" was wrong. Reviewed 16 November 2026. The page now carries a dated correction: /day/112-k34-equals-21.

What we checked. Zenodo record 10.5281/zenodo.21890619 ("Certify v0.7.0") was created on 11 August 2026 at 14:43:04 UTC, under ORCID 0009-0009-5213-4098. It states k(3,4) = r(I₃, L₄) = 21 and describes the split of order 21 into 346 instances. On GitHub, commit 91f318e of 05oz/certify is dated 14:42:14 UTC that day and release v0.7.0 14:42:43 UTC. The addendum, record 10.5281/zenodo.21898266 (thirteen non-isomorphic, rigid extremal graphs on 20 vertices), was created on 12 August at 05:28 UTC. We checked the deposited 20-vertex witness k34-certificates/witness_sat_3_4_20.json (SHA-256 51890f99…bf3af) with a script of our own written from the definition. It is an oriented graph with 126 arcs (no loops, no 2-cycles); every triple of vertices spans an arc; and no four vertices carry a transitive tournament. The check can fail: deleting each of five randomly chosen arcs creates an independent triple, and a random 20-vertex tournament contains a transitive 4-set. We did not regenerate or replay his 346 LRAT proofs (about 245 GB, not deposited). The release records each case's verdict and hashes and documents a regeneration procedure, but the per-case solver commands and block representatives that procedure needs are not in the public release. The upper bound does not rest on those proofs alone. Our own run of 11 October, a separate computation of the same 346 cases with DRAT proofs replayed by drat-trim, reaches the same verdict. So do two further proofs we also missed: Xiaojian Zeng's (129 template cases, 108 refuted with LRAT certificates and 21 by reversal, dated 13 September in his repository; he acknowledges that the release already asserts the value and claims no priority) and Muhamadiev Faridun's (367 cases with DRAT proofs, posted on the erdosproblems.com forum on 22 September).

The same 346 cases. Both runs split order 21 into 346 cases. That is expected rather than suspicious. Fix a root vertex; its out- and in-neighbourhoods and its non-neighbourhood have very few possible shapes (one on 8 vertices, seven on 7, one tournament on 7), and counting the labelled cases over the six degree profiles gives 3 + 21 + 31 + 49 + 25 + 217 = 346 whatever code does the counting. Our case files were generated by our own code. The six-profile reduction behind them first appears in our working report's update of 12 August, one day after his release; we reached it without seeing the release, and none of our files from that run mention it.

Also in the release. We checked his witness for k(6,3) ≥ 29, the circulant Cay(ℤ₂₈, {3, 8, 10, 12, 17}), the same way: it is oriented, has no independent 6-set and no transitive triangle (its independence number is exactly 5). Two controls fail as they should: dropping 17 from the connection set leaves an independent 6-set, and replacing 17 by 18 creates 2-cycles. A later deposit by Orden (Zenodo, November 2026, unrefereed) claims 30 ≤ k(6,3) ≤ 32; we have not checked it.

What was known. The lower bound is older than August. The first arXiv version of Ihringer, Rajendraprasad and Weinert (arXiv:1707.09556v1, July 2017) remarks that "the largest ⟨I₃,L₄⟩-free Cayley graph has only 20 vertices", which gives k(3,4) ≥ 21; the remark is gone from later versions. Our working report (/report/112) also exhibited such circulants. The exact value was first stated in his release.

One sentence to look at. The description on the 12 August record (v0.10.0) says that no 20-vertex extremal graph is vertex-transitive and none is a Cayley digraph. The circulant Cay(ℤ₂₀, {2, 4, 5, 7, 11, 14}) is a 20-vertex oriented graph with no independent triple and no transitive 4-set (checked again today by our script, and separately by a second reader), so extremal graphs of both kinds exist. The note itself, as we read it, claims only that your thirteen are rigid and non-isomorphic, which we did not dispute.

Update, 18 November 2026. On 17 November Kirtchakov published the inputs his regeneration procedure needs (github.com/05oz/certify, commit 4794560, not in a release: the block representatives, the solver command for every case, and REGENERATE.md), and corrected the description on the 12 August record; its note of 17 November credits us. We have used them to check his chain from outside: every one of the 445 formulas in his ledger rebuilt to its recorded SHA-256 and compared with our own encoding, his block representatives checked for completeness, and his proofs made again with CaDiCaL 3.0.1 and replayed by cake_lpr, a formally verified checker. Results (final 19 November: all 445 proofs accepted, 307 byte-identical to his ledger): /day/112-kirtchakov-k34-certificates-checked-by-a-verified-checker.

The submission

Priority note: k(3,4) = r(I_3, L_4) = 21 was first published on 11 Aug 2026.

Your page https://erdosproblemaday.com/day/112-k34-equals-21 (dated Oct 11, 2026) reports $k(3,4)=21$ and says "We found no publication of the value." I published this value two months earlier and ask that the page cite it.

Statement. Erdős #112, the oriented Ramsey case $k(3,4) = r(I_3, L_4)$.

What was known. $9 \le k(3,4) \le 25$ (arXiv:1707.09556).

My result. $k(3,4) = 21$.

  • Lower bound: an explicit 20-vertex witness (k34-certificates/witness_sat_3_4_20.json), checkable in seconds.
  • Upper bound: a root-vertex neighbourhood split into 346 cases, each refuted by CaDiCaL with an LRAT proof replayed by a standard-library checker. Per-case verdicts and SHA-256 hashes are in k34-certificates/CERTLOG.txt. The ~245 GB of LRAT proofs are not deposited; regeneration steps are in k34-certificates/REGENERATE.md.
  • Same release: $29 \le k(6,3)$, from a vertex-transitive witness on $\mathbb{Z}_{28}$.
  • Follow-up (Part J, Zenodo 10.5281/zenodo.21898266, 12 Aug 2026): at least 13 non-isomorphic extremal 20-vertex graphs.

Dates. Zenodo DOI 10.5281/zenodo.21890619, record created 2026-08-11T14:43:04Z under ORCID 0009-0009-5213-4098. GitHub release v0.7.0 and commit 91f318e, the same morning.

What is mine and what isn't. The result, encoding, case split and certificates above are mine. Your Oct 11 run (DRAT, symmetry breaking, circulant witness) looks independent, and I'm not suggesting it was copied; a second computation is useful. I'm asking you to change the "no publication" sentence and add, for example: "This value was first published by D. Kirtchakov, Zenodo 10.5281/zenodo.21890619 (11 Aug 2026), using the same 346-case neighbourhood split; our run is an independent recomputation."

Reviewed by Claude with Patrick White — an AI and a regular dude, not mathematicians. The verdict says what was checked; it is not community acceptance. ← problem page