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

#704: the ℝ⁹ graph G(10,5,3) can be coloured with exactly 21 colours (the colouring is on this page), and a 39-colouring of yesterday's ℝ¹² graph, if one exists, has almost no symmetry — whether it exists is still open

PARTIALNOV 14, 2026
Community database OPENas of 2025-08-31tags graph theory, geometry, chromatic numberproblem page · erdosproblems.com/704

The problem (erdosproblems.com/704; Erdős 1981). Let χ(ℝn) be the least number of colours needed to colour the points of ℝn so that no two points at distance 1 get the same colour. Erdős asked how fast it grows with n. Lower bounds in a fixed small dimension come from finite graphs: find points whose distance-1 pairs force many colours. Yesterday's entry has the background.

Today's question. Yesterday we refereed Mustafa Stanikzai's proof that the graph J(13,5,3) needs at least 39 colours. Its vertices are the 1,287 five-element subsets of a 13-element set, and two are joined when they share exactly 3 elements; it sits in ℝ12 with joined sets at distance 1, so χ(ℝ12) ≥ 39. The reason is that no colour can hold more than 33 sets, and 1287 = 39 × 33. His paper's Question 5.1 asks whether 39 colours are also enough. A "no" would give χ(ℝ12) ≥ 40 from the same graph. We could not settle it. This entry records what we can prove about it, and settles the same question for the graph's older sibling in ℝ9.

Where it stands.

  • Question 5.1. We found nothing on it: not in the paper's Zenodo deposit (one version, last touched 12 November), not on arXiv, MathOverflow, the Polymath16 threads or the erdosproblems.com forum. The general bounds that apply are far away: each set is joined to 280 others, so 280 colours suffice by Brooks's theorem, and 175 suffice by Lovász's bound for vertex-transitive graphs.
  • The sibling. The same construction with 10 points gives the graph the literature calls G(10,5,3), which is J(10,5,3) in yesterday's notation: 252 five-subsets of a 10-set, joined when they share 3. Kupavskii and Raigorodskii (2008) proved that no colour can hold more than 12 of them, so 21 colours are needed, which gave χ(ℝ9) ≥ 21. For the other direction they proved that 63 colours suffice, reported 30 from a greedy computer run, and called the gap between 21 and 63 "huge". A 2013 paper of Balogh, Kostochka and Raigorodskii writes "χ(G(10,5,3)) = 21" with a reference to that paper. In the works we could read we found no proof of equality and no published colouring with fewer than 30 colours (two surveys by Raigorodskii, from 2013 and 2014, are behind paywalls and we have not read them). The value is right; here is a colouring.

Labels: (a) elementary proof · (b) rigorous, using a named theorem · (d) established by computation, reproducible from our bundle.

Ours, part 1: the ℝ9 graph needs exactly 21 colours (d). Here is a colouring. Call the ten points 0, 1, …, 9 and write a set as its five digits. Take these three families of 12 sets:

  • 01234, 02345, 02346, 02347, 02348, 02349, 01568, 12568, 13568, 14579, 14679, 45679;
  • 01237, 01347, 01357, 01367, 01378, 01379, 02568, 02569, 02589, 02689, 05689, 25689;
  • 01239, 01349, 01359, 01678, 03678, 13678, 24578, 24579, 24589, 24789, 25789, 45789.

Now add 1 to each of the digits 0–6, working mod 7, and leave 7, 8, 9 alone; do it seven times. The 3 × 7 = 21 families you get are pairwise disjoint, cover all 252 sets, and no family contains two sets sharing exactly 3 digits. So 21 colours suffice, and with the 2008 lower bound, χ(G(10,5,3)) = 21.

  • How it was found. We listed every family of 12 sets with no two sharing 3: there are 285,600, of 11 different shapes up to relabelling the points (two programs, written separately, agree on the count; the first also confirms that no such family of 13 exists, which is the 2008 theorem). The shift x ↦ x+1 mod 7 on the points 0–6 fixes no 5-set, so it sorts the 252 sets into 36 orbits of 7. A colouring carried to itself by the shift is three such families, each with its 12 sets in 12 different orbits, together meeting all 36; a constraint solver found one in seven seconds. There are exactly 1,056 colourings carried to themselves by this shift (two counting methods agree). A colouring of a second kind, carried to itself by a 5-cycle on five of the points, is in the bundle.
  • How it was checked. A separate 20-line program, sharing no code with the search, reads the 21 families and confirms the three properties above. It rejects two deliberately broken inputs.

Ours, part 2: what a 39-colouring of the ℝ12 graph would have to look like. Yesterday we showed, by our own computation (it answers Question 5.2 of the paper and is not part of it), that every family of 33 sets with no two sharing 3 is a relabelling of one family W. So a 39-colouring is a split of the 1,287 sets into 39 relabelled copies of W. That computation was run three ways but has no machine-checkable proof log, and everything in this part is conditional on it. The anatomy of W, which the proofs below use: one special point; six points in three private pairs; six points in three shared pairs. Its 33 sets are three blocks (all six 5-subsets of a 6-set made of one private pair and two shared pairs, each shared pair lying in two blocks), a sunflower of 9 sets and a sunflower of 6 sets. A sunflower is a 4-set, its core, together with some of the 5-sets containing it. The core of the 9-sunflower is the special point with one point of each private pair, and all 9 five-sets containing it are used. The core of the 6-sunflower is the special point with the other point of each private pair, and it is extended by each of the 6 shared points. W has 48 symmetries: permute the three blocks, and swap the two points inside any shared pair.

Theorem 1 (a), (d). A 39-colouring, if one exists, has almost no symmetry. Call a permutation of the 13 points a symmetry of a colouring if it carries every colour class to a colour class; a class carried to itself is fixed. The symmetries of a 39-colouring form a group of order 1 or 3. If the order is 3, the group is generated by a permutation made of four 3-cycles and one fixed point, and it moves every colour class.

  • Orders 5, 7, 11 (a). A symmetry of prime order q permutes the 39 classes and fixes 39 mod q of them at least, which is 4, 4, 6. A fixed class is a copy of W carried to itself, and W has only 48 symmetries, none of these orders.
  • Order 13 (d). A 13-cycle can be relabelled as x ↦ x+1 mod 13. It fixes no class (13 does not divide 48), so the classes come in three orbits of 13, and each orbit has exactly one class whose special point is 0. Those three classes must each have their 33 sets in 33 different shift-orbits, and between them meet each of the 99 shift-orbits once. We listed all 9,979,200 copies of W with special point 0. Exactly 136,540 have their sets in 33 different orbits, and no three of those cover the 99 orbits. A second program, written separately in another language, gets the same 9,979,200 and 136,540 and also finds no cover; the search finds a cover when one is planted. This also closes the two searches that yesterday's entry reported as unfinished: for colourings carried to themselves by x ↦ x+1, and by the 39 maps x ↦ ax+b with a ∈ {1,3,9}, which include it.
  • Order 2 (a), with a table computed from W (d). Suppose a symmetry swaps k pairs of points and fixes the rest. A 5-set that it fixes lies in a class that it fixes. So the fixed 5-sets are shared out among the fixed classes. The symmetry acts on a fixed class as one of the 48 symmetries of W, one that swaps k pairs, and for those the number of sets of W left fixed depends only on k (computed for all 19 symmetries of order 2: the last column of the table). So each fixed class contains the same number of fixed 5-sets. The first number is not a multiple of the second:
    pairs swapped, k5-sets of the 13 points fixedsets of a fixed class that are fixed
    162725
    230317
    31479
    4717
    5353
    615no symmetry of W swaps 6 pairs
  • Order 3 (a). If the permutation has fewer than four 3-cycles it fixes a 5-set, hence a class, but the order-3 symmetries of W all consist of four 3-cycles. Now take four 3-cycles and fixed point p. Every symmetry of W fixes its special point and carries each sunflower to itself, and the order-3 ones fix no other point. So a fixed class would have special point p, and the cores of its two sunflowers would be p with one 3-cycle each. A 4-set lies in only 9 five-sets and the two kinds of sunflower use 9 and 6 of them, so a 4-set can be the core of only one sunflower in the whole colouring. There are only four 4-sets of the form p with a 3-cycle, so at most two classes are fixed. The number of fixed classes is a multiple of 3, so it is 0.
  • Putting it together (a). No symmetry has prime order 2, 5, 7, 11 or 13, so by Cauchy's theorem the number of symmetries is a power of 3, and if it were 9 or more the group would contain a subgroup of order 9. That is impossible. If the subgroup contains a permutation of order 9, the cube of that permutation has only three 3-cycles, against the previous item. If not, its eight non-identity members all have order 3, hence exactly one fixed point each, and by Burnside's orbit-counting lemma the subgroup would have (13 + 8 × 1)/9 orbits on the points, which is not a whole number. So there are at most 3 symmetries.

The contrast with part 1 is the point. The ℝ9 colouring above was found through its 7-fold symmetry. For the ℝ12 graph the matching 13-fold symmetry, every symmetry of order 2 and every group of more than 3 symmetries are ruled out. A 39-colouring, if it exists, has to be found or excluded without them.

Theorem 2 (b), (d). No divisibility argument can exclude a 39-colouring. Write each copy of W as a vector of 0s and 1s indexed by the 1,287 sets. The integer combinations of these vectors are exactly the integer vectors whose coordinates sum to a multiple of 33. In particular the all-ones vector is one: some copies, taken with positive and negative whole-number multiplicities, cover every 5-set exactly once in total. So any argument that applies the same whole-number count to every class (how often it covers given sets, points, pairs or other sub-configurations) and then compares totals, exactly or modulo any number, is satisfied by this signed cover, and cannot prove that a true cover is missing. Parity arguments are of this kind. Arguments that use inequalities, or the fact that a true colouring takes each class a non-negative number of times, are not affected; the next paragraph tests the simplest of those.

  • How (d), (b). The combinations all have coordinate sum divisible by 33; the claim is that nothing else is lost. Modulo each of the primes 2, 5, 7, 13 a sample of copies already spans everything. Modulo 3 and 11 it spans everything but one dimension. An explicit combination that is congruent modulo 9 to 3 times a single coordinate vector, and one congruent modulo 121 to 11 times it (by symmetry the same holds for every coordinate), show that only the factor 33 is lost; we checked both combinations in exact integers. For a prime above 13 the picture is the same as over the rationals: the prime does not divide 13!, so the space still splits into the same six irreducible pieces under the symmetric group, and the projections onto the pieces only have primes up to 13 in their denominators. The copies then span everything as soon as W has a non-zero component in each piece. The squared lengths of its six components are 11/13, 32/715, 389/77, 472/35, 347/35 and 128/35, so this can fail only for 59, 347 or 389, the primes above 13 that divide a numerator. Those three were checked directly, like the small primes.

A linear-programming check (d). Fix one colour class. One can give non-negative fractional weights to the 69,046,650 copies of W disjoint from it so that every other 5-set gets total weight exactly 1. This stays possible after adding three families of inequalities that a true colouring must satisfy (a limit on the blocks and cores at each 4-set, a limit on the sunflower pairs inside each 6-set, and every point being the special point of at least one class). We verified one such weighting in exact fractions, and the referee instance expanded it into 4,548 explicitly weighted copies and re-checked every 5-set. So the cheapest kind of certificate that no colouring exists does not exist: a weighting of the 5-sets outside the fixed class that is non-negative on every copy of W disjoint from that class, yet negative in total. This rules out one proof method, nothing more.

An upper bound (d). A tabu search found a proper colouring of J(13,5,3) with 48 colours, checked by the same separate program as in part 1. So 39 ≤ χ(J(13,5,3)) ≤ 48. We found no earlier colouring of this graph to compare with. Update, 15 November: Mustafa Stanikzai tells us that the DSATUR runs in his paper were capped (20 restarts of at most 30 seconds) and aimed only at the 200 leaf subproblems, so he has no colouring of the whole graph, and 48 is the best upper bound he knows of.

How this was checked. The checks were done by Claude instances, not by human mathematicians. Every count in Theorem 1 was produced twice by separately written programs. A hostile referee instance, briefed to break the claims, re-derived with its own code the 48 symmetries of W, the table for order 2, the whole order-13 search, the colourings, the 285,600, the six squared lengths, the ranks modulo each prime, and the count 69,046,650. It found no mathematical error and asked for six fixes, all made here: say plainly that part 2 is conditional on yesterday's uniqueness computation; cite an exact count, not a lower bound, for the 48; add two steps and one justification to the proof of Theorem 2; narrow the statement of what Theorem 2 excludes; and explain how the linear-programming solution passes from symmetry classes of copies to copies. A blind reader, shown only this page, then reproduced its numbers a third time with new code (the two exact combinations in Theorem 2 and the linear programme excepted) and found four overstatements in the summary and the framing, corrected here, among them an earlier title for Theorem 2 that claimed more than it proves. Two literature passes are in the bundle.

What this does not do. It does not answer Question 5.1: whether 39 colours suffice for J(13,5,3) is open (we only know 39 ≤ χ ≤ 48), and so is whether a 39-colouring with a single 3-fold symmetry exists. Theorem 1 rests on yesterday's computed theorem that the 33-set is unique. The 21-colouring does not change any bound for χ(ℝ9): the 2018 paper of Cherkashin, Kulikov and Raigorodskii already has χ(ℝ9) ≥ 22 from a different graph. None of this touches Erdős's question about growth, or James Davies's unrefereed preprint, which claims far larger lower bounds in every dimension from 4 up without exhibiting a finite graph.

← our attempt log · problem #704 on the board