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

A verified partial result (a case, a bound, an exact value)

VERIFIED2026-11-12 · ANONYMOUS
Community database OPENas of 2025-08-31tags graph theory, geometry, chromatic numberproblem page · erdosproblems.com/704
Our review · 2026-11-13

Verdict: VERIFIED. α(J(13,5,3)) = 33, so χ(ℝ¹²) ≥ ⌈1287/33⌉ = 39 from an explicit 1,287-vertex unit-distance graph. Reviewed 13 November 2026. Full write-up, with our code and logs: /day/704-chi-r12-39-refereed-and-the-33-set-is-unique.

The claim. J(13,5,3) is the graph on the 5-subsets of {1,…,13}, with two subsets joined when they share exactly 3 elements. Send each set to half its indicator vector: the points lie in the hyperplane Σx = 5/2, and joined sets are at distance 1. The paper (Hexagon 2611.00358; Zenodo 10.5281/zenodo.24145863) proves α = 33. The lower bound is an explicit 33-set. The upper bound fixes one vertex and uses orbital branching to cut the problem into 200 clique problems. Each is refuted by the Glasgow Subgraph Solver, and VeriPB accepts its proof log.

What we checked. We did not re-run VeriPB; the logs are 1.26 TB unpacked. We checked the bound another way.

  1. A second derivation by a different tree. It is our own code from the definition, using the same technique, orbital branching, from a different root. A family with all pairwise intersections ≤ 2 has at most 28 members (286 triples, 10 in each set), so a 34-set contains two sets sharing 4 elements. We fix that pair, which leaves 851 other candidate sets at threshold 32. Those split into 105 leaves. Our own solver refutes all 105, and so does cliquer 1.21, a different method (Östergård's). An independent replay program accepts the tree and rejects six broken versions of it. As controls, the same tree finds 33-sets, and on smaller graphs it gives α(J(10,5,3)) ≤ 12 and α(J(11,5,3)) = 18; CP-SAT on the whole graphs agrees. These are solver verdicts without proof logs, so they corroborate your certified chain rather than replace it.
  2. Your 200 leaves. Your leaf files equal the complement of J on the mapped 5-sets, and each threshold is 33 − |F|. Our solver finds no clique at threshold in any of the 200, and your five colouring certificates check.
  3. Literature. The largest bound stated in print from an explicit graph was 37 (Cherkashin–Kulikov–Raigorodskii 2018). Exoo–Ismailescu's reported α(J(13,6,4)) = 46 gives 38 but was stated as 36. Davies's unrefereed preprint arXiv:2610.12301 gives 164 and 2,516, from no exhibited graph. Your paper says all of this correctly.

Your Question 5.2: yes, by an uncertified computation. Every maximum independent set of J(13,5,3) is a relabelling of your Appendix A family. Its symmetry group has order 48, so there are 13!/48 = 129,729,600 of them. We listed every 33-set in every leaf of three trees: ours, a finer refinement of ours, and your 200 leaves at threshold − 1. All of them have one nauty canonical form. So a 39-colouring (your Question 5.1) would have to be 39 disjoint copies of that one family. We have not settled whether such a partition exists.

Tools, as declared by the submitter: Claude Opus 5.5, Fable 5, 5.1, & 5.2. GPT-5.6-sol

The submission

The problem remains open. I have a small result on it for one dimension: χ(R^12) ≥ 39, from an explicit finite unit-distance graph. Earlier explicit graphs give at most 38. Davies's recent preprint gives much larger bounds by other methods.

The proof is by computer. All the machine-checkable proof logs and the programs are public with the paper.

Paper: https://hexagonmath.org/2611.00358 Proof logs and programs: https://doi.org/10.5281/zenodo.24145863

I used AI tools in the work and the paper says how.

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