5 : 3 · major sixth
← All deep dives
ongoing / / 16 min read

Four days with the 509: searching for the smallest graph that needs five colours

Claude and I tried to beat the 509-vertex record for the plane’s chromatic number. We didn’t. We found a 509 built on a different foundation, took the record apart, and learned exactly why it is so hard to shrink.

Some problems are easy to state and refuse to be solved. This is one of them: how many colours do you need to colour every point of the plane so that no two points exactly one unit apart share a colour?

For four days in November, Claude and I tried to push one small corner of it forward. The goal was concrete: find a unit-distance graph that can’t be coloured with four colours, using fewer than 509 points. Five hundred and nine has been the record since 2020. We didn’t beat it. What we found instead was a graph of exactly 509 points built on a different foundation from Parts’ own, a much clearer picture of how the record works, and a long list of exact proofs that the obvious ways to improve it go nowhere.

This is the story of those four days: what we tried, what each attempt taught us, and how we got to where we are.

#The question

In 1950 Edward Nelson asked for the chromatic number of the plane: the smallest number of colours that can colour every point of the plane so that any two points at distance exactly 1 get different colours. Nobody knows the answer. For almost seventy years, all anyone could say was that it is one of 4, 5, 6 or 7.

The upper bound is a tiling. Cover the plane with hexagons slightly smaller than one unit across, colour them with seven colours in a repeating pattern, and no two points one unit apart ever land in hexagons of the same colour.

The lower bound comes from small, clever graphs. If you can place a few points in the plane, join every pair that is exactly one unit apart, and show that the result can’t be coloured with k colours, then the plane can’t either. The classic example is the Moser spindle from 1961: seven points, eleven unit-length edges, and no way to colour it with three colours. Try it:

Seven points, three colours. Try it.

Click the points to colour them. Every line is one unit long, and its two ends must differ.

The reason it fails is pleasingly simple. Each half of the spindle is a rhombus made of two equilateral triangles. With three colours, the far tip of each rhombus is forced to have the same colour as the shared bottom point. The two rhombi are turned apart by exactly the angle that puts their tips one unit from each other, so the tips must differ, which they can’t.

That turning angle is worth remembering. Two points at distance 3\sqrt{3} from a centre are one unit apart when the angle between them is θ\theta with

23 sin⁡θ2=1⟹cos⁡θ=56.2\sqrt{3}\,\sin\frac{\theta}{2} = 1 \quad\Longrightarrow\quad \cos\theta = \frac{5}{6}.

Twists like this, a rigid piece and a rotated copy of it, are the heart of everything that follows.

In April 2018, Aubrey de Grey, best known for his work on ageing and an amateur mathematician, found a graph with 1,581 points that cannot be coloured with four colours.1 The lower bound jumped from 4 to 5 overnight. A collaborative Polymath project and a series of computer searches then shrank the example: Marijn Heule found graphs of 553 vertices and fewer, and in 2020 Jaan Parts published a graph with 509 vertices and 2,442 edges.2 As far as anyone knows, that is still the smallest.

Published Ours de Grey 2018, the first one 1,581 Heule 2018–19, computer searches 553 Parts 2020, the record 509 Our construction built from our own generators 1,078 Our own graph 15 Nov, morning 600 Our own graph 16 Nov, after exact swaps 589 The new 509 16 Nov, on a different S half 509
Sizes of 5-chromatic unit-distance graphs. Fewer vertices is harder. Our search tied the record but didn’t beat it.

Smaller graphs matter because they are easier to understand, and understanding is what might eventually tell us whether the answer is 5, 6 or 7. A 509-point graph is still far too big to check by hand. Every step down is a step toward a proof a human can read.

#What counts as a result

Before any search, we agreed on what would count. It matters more than anything else in a project like this, because a computer search produces a lot of things that look like results.

A graph counts only if one script says VALID. That script checks three things:

  1. Every edge is exactly one unit long. Not approximately: exactly. All our points live in the number field Q(3,5,11)\mathbb{Q}(\sqrt{3}, \sqrt{5}, \sqrt{11}), and every distance is computed with exact rational arithmetic over that field. Floating-point coordinates are used for drawing pictures and nothing else.
  2. All points are distinct, and every pair of points at unit distance really is an edge.
  3. The graph cannot be 4-coloured. This is turned into a logic puzzle a SAT solver can answer. Give each vertex four yes/no variables (“vertex v has colour c”), require every vertex to have at least one colour, and forbid both ends of an edge from sharing one:
def four_colouring_cnf(n, edges):
    var = lambda v, c: 4 * v + c + 1
    clauses = [[var(v, c) for c in range(4)] for v in range(n)]      # every vertex gets a colour
    clauses += [[-var(a, c), -var(b, c)] for a, b in edges for c in range(4)]  # edges differ
    return clauses

For a 509-vertex graph with 2,464 edges, that is 2,036 variables and 10,365 clauses. If the solver proves there is no satisfying assignment, there is no 4-colouring. The answer we hope for is always “unsatisfiable”.

#Our own graph: from 1,078 to 589

We started the way most people would: build a big graph we understand, then delete points until we can’t delete any more.

Our first graph had 1,078 points, generated in the exact field from a handful of rotations and the hexagonal lattice. A SAT solver confirmed it couldn’t be 4-coloured. Then came the shrinking. Delete a point, ask the solver whether the rest is still not 4-colourable, keep the deletion if it is, undo it if not. Clever versions of this (remove a group, refill with fresh points, accept sideways moves) took the graph to 604, then to 600.

By the morning of 15 November we were stuck at 600. Deleting any single point made the graph colourable. Every refill brought us back to 600 or worse.

The next idea was better: instead of only deleting, swap. Take a vertex out and look for a single new point somewhere in the plane that keeps the graph uncolourable. And don’t guess where: a useful new point has to be one unit from at least four of the existing points, otherwise it can always just take a spare colour. There are only finitely many such points, and they can be computed exactly as intersections of unit circles. With every candidate checked exactly, the descent found its way down: 600, 593, 591, 590, and finally 589 in the early hours of 16 November.

Five hundred and eighty-nine was progress, but it was still 80 points from the record, and the descent had slowed to a crawl. It was time to change approach. Instead of polishing our own graph, we decided to study the record itself, to understand exactly why it works and where, if anywhere, it might give.

#Taking the record apart

Parts published his graph together with a description of how it was built, and the first thing we did was check that description against the data. It holds exactly.

The 509 is two pieces glued together at a single point:

  • L, 374 points of one lattice (the centre included).
  • S, 135 more points of the same lattice, rotated about the centre by the angle ρ\rho with cos⁡ρ=7/8\cos\rho = 7/8.

Every point of L has coordinates of the form

z  =  a+b3312  +  i c3+d1112,z \;=\; \frac{a + b\sqrt{33}}{12} \;+\; i\,\frac{c\sqrt{3} + d\sqrt{11}}{12},

with integers a,b,c,da, b, c, d obeying a couple of parity rules. Rotating by ρ\rho brings in sin⁡ρ=15/8\sin\rho = \sqrt{15}/8, and with it a 5\sqrt{5}. That gives an exact test of which half a point belongs to: lattice points never contain 5\sqrt{5}, twisted points always do.

The two halves share only the centre and are tied together by just 18 edges. That is the surprising part: 509 points and 2,442 edges, and the whole proof hinges on 18 edges between two otherwise independent pieces.

Why cos⁡ρ=7/8\cos\rho = 7/8? Look at the points two units from the centre. Two such points at angle θ\theta apart are one unit from each other when

4sin⁡θ2=1⟹cos⁡θ=1−2⋅116=78.4\sin\frac{\theta}{2} = 1 \quad\Longrightarrow\quad \cos\theta = 1 - 2\cdot\frac{1}{16} = \frac{7}{8}.

It is the spindle trick again, one level up: instead of rotating a rhombus, Parts rotates half a lattice. Here is the interface between the halves, the 18 points on each side that the 18 edges connect. Turn the twisted half and watch when they meet:

Drag the slider to turn the twisted half. A pair lights up when its two points are exactly one unit apart.

Most angles bring only a handful of pairs together. At about 31°, the mirror image of the twist, the twelve points on the ring of radius 2 line up, but the six on the two inner rings don’t. Only at exactly arccos⁡(7/8)≈28.955°\arccos(7/8) \approx 28.955° do all 18 pairs meet at once.

#The two statements that clash

Knowing the structure, we could ask what each half actually does. With the SAT solver as a microscope, we enumerated every way the S half allows its 18 interface points to be coloured: 44,090 patterns. Then we tested which of them the L half can live with. None, of course, but the reason turned out to be clean:

  • L says: in every 4-colouring of L, every run of three neighbouring points on a ring hexagon contains at least one point with the centre’s colour.
  • S says: in 99.6% of its colourings, some small set of ring points, usually three neighbours, all take the centre’s colour.

The twist matches each ring point of S to a ring point of L one unit away, neighbours to neighbours. So if S paints three neighbours in the centre’s colour, their three partners in L must all avoid it, which is exactly what L forbids. The remaining 0.4% of patterns are killed by 65 messier, mixed constraints, and covering them costs S extra points.

The accounting was revealing too. About 305 of L’s 374 points are needed for any statement about the ring at all. The rest are “wings” serving particular patterns. And every single one of S’s points is needed: remove any one, and some colouring slips through.

#How we worked

I should say a word about how this was done, because the method was half the experiment.

The main session, Claude working with me, acted as coordinator. It wrote short briefs and handed them to parallel cloud sessions, more than twenty over the four days, each running one search on its own machine and reporting back through the repository. Early on, a brainstorm of a hundred small agents produced a ranked list of ideas, which we pruned hard. Later, four “think-tank” sessions were asked for something different: no searching, just ideas grounded in the facts so far, each with the cheapest experiment that could kill it. One of them was told to be the critic.

Two rules held the whole thing together. The VALID script was the only judge: an agent’s claim was just a claim until the script agreed. And every negative result was written down with the exact conditions under which it holds. That second rule turned out to be the more important one, because most of what we learned came from careful negatives.

#Is the 509 a dead end?

The most direct question: can the 509 be improved by small changes? We asked it in the strongest form we could make exact.

Swaps. We computed every point in the plane that is one unit from at least four vertices of the 509: 697 of them. For each vertex, we tested exactly which of these points could replace it. There are exactly 11 one-for-one swaps, no point that can replace two vertices at once, and no pair of points that can replace three. In this neighbourhood, the 509 is locally optimal.

The plateau. Each one-for-one swap leads to another 509-vertex graph, and you can walk from one to the next. We checked about 230 of them, up to 15 swaps away from the original, for any way down. None exists, and only 23 of the 509 positions ever change along the way. The record sits on a small, flat plateau.

Whole regions. Swaps change one or two points. To test bigger changes, we freed every vertex inside a disc and asked an exact solver whether the disc could be refilled with fewer points, choosing from every candidate we knew. For discs of radius 0.6, up to 57 vertices freed at a time, every one of the 53 discs came back the same: no smaller refill.

Exact lower bounds. The strongest results came from fixing a shared core and proving the minimum over everything else. Parts’ 509 and Heule’s 510 share 466 points. With those fixed, the smallest set of extra points that makes the graph uncolourable can be found exactly, with a technique called an implicit hitting set: every 4-colouring found along the way rules out a small family of candidate sets. We ran it on three growing pools of free points: the points where the two graphs differ, then those plus Parts’ alternative pieces, and finally every point we had seen anywhere in the search.

Shared coreFree pointsResultTime
46687509 is the minimum4 min
466132509 is the minimum10 min
456283nothing with 508 or fewer—

These proofs are only as wide as their universe, and we were careful to say so every time. Within everything we could name, 509 is the floor.

#A 509 on a different foundation

First, a word on what “new” means here. The 509 isn’t a single graph. Parts himself found many minimal versions of the L half, each of which gives a valid 509 together with his S half, and the plateau above is full of 509s one swap apart. What all of those share is Parts’ S half. So the real question was whether the record size can be reached from a different S half altogether.

On the evening of 16 November, the second starting point answered it.

Heule’s published 510 has the same two-piece structure as Parts’ 509, but with a genuinely different S half, not a symmetric copy. So we mixed and matched: every L half against every S half, in every rotated and mirrored position. The finished halves, swapped between the two graphs, could all be coloured. But Parts’ broader family of 412 L points, set against Heule’s S, could not. Shrinking it gave a 510, and one exact two-for-one swap took it to 509 vertices and 2,464 edges.

It contains all 135 points of Heule’s S half, which is not one of Parts’: six of its points lie outside every S half Parts published. Its L half is a 374-point piece of Parts’ L family. It shares 472 points with Parts’ 509 and differs in 37. And it has a property neither original has: its L half is the only one we found that works with three different S halves, Parts’, Heule’s, and the S of Heule’s 529.

374 points of the lattice half (dark, the centre included) and 135 of the twisted half (accent). They meet at the centre and are tied together by just 18 edges (thick).

So the record size isn’t tied to Parts’ S half: it can be reached from at least two different S families. That doesn’t move the number, but it shows the 509 isn’t an accident of one particular construction.

#Hidden symmetry

One of the prettiest findings came from looking at the numbers instead of the picture.

Every coordinate is a combination of 3\sqrt{3}, 5\sqrt{5} and 11\sqrt{11}. Algebra lets you flip the sign of any of those roots consistently, and it still gives valid unit distances. These Galois symmetries aren’t rotations or reflections of the plane in any ordinary sense. They scramble the picture. But combined with a mirror, flipping 5\sqrt{5} maps 493 of Parts’ 509 points exactly onto other points of the graph. In our new 509 the same symmetry fixes 485.

So the record is almost symmetric under a symmetry you can’t see by looking at it. The few points that break it turned out to be exactly the ones that move on the plateau. We tried the obvious next step, insisting on the symmetry exactly, and it costs points every time:

Symmetry kept exactlySmallest graph found
flip 5\sqrt{5} + mirror511
either of the other two single flips512
both flips (a group of four)513
with the 120° rotation (groups of six)520 and 523
all twelve together526

Symmetry is beautiful, but here it is slightly too expensive. The record lives in the small imperfections.

#Trading between the halves

If neither half can be shrunk in place, maybe one half could get smaller while the other pays a little more. We tested this directly by making one side unlimited and searching hard on the other.

With L replaced by a whole patch of the lattice, every point of S is still needed, but exact swaps found something new: S halves with 134, 133, 132 and even 131 points, against Parts’ 135. Each one is genuinely smaller. The catch is the price on the other side:

S halfL half it needsBest total found
135 (Parts)374509
134376510
133379512
132381–382513–514
131379510

Every smaller S has needed a bigger L, and so far the total has never dropped below 510. Going the other way was worse: with S unlimited, L shrinks to about 350, but then no single point, and no small group, can pay for the difference. S additions only work in blocks of hundreds. The two halves are balanced at the record, and that balance is a big part of why it is hard to beat.

#Why this twist, and no other

The last big question was the twist itself. Is cos⁡ρ=7/8\cos\rho = 7/8 just the first angle someone tried?

We built lattice pieces for many other ring radii and twist angles and tested them exactly. A twist by the unit-chord angle of a ring of radius RR, with cos⁡θ=1−1/(2R2)\cos\theta = 1 - 1/(2R^2), can only touch the base lattice where the lattice has points of length RR in every one of its algebraic “shadows”. Working that condition out exactly up to R2=30R^2 = 30, and testing every twist that can touch at all, gave a clean answer: within this lattice, Parts’ twist is the only one that works. Some twists have seven times as many contacts as Parts’ and can still be 4-coloured. What matters is how the rings of contacts interlock, not how many there are.

There is a pleasant footnote here for anyone who likes the golden ratio, which I do. The interference pattern between the lattice and its twisted copy has an irrational ratio of 3(4R2−1)\sqrt{3(4R^2 - 1)}. For R=2R = 2 that is 45=35\sqrt{45} = 3\sqrt{5}, which ties the record’s twist to φ\varphi, the golden ratio. Of every radius we checked, R=2R = 2 is the only one that is both touchable and golden. I don’t claim that this explains anything. But it is the kind of coincidence that makes you look twice.

#What didn’t work

A partial list, because the negatives took most of the time and taught most of the lessons:

  • Re-shrinking big pools in random orders. From our own pools we got 644–765 points; from Parts’ own families of alternative pieces, 519–525. Shrinking finds local minima, and this landscape is full of them.
  • Placing the two halves differently. About 173,000 rigid placements of Parts’ S against his L, plus algebraically conjugate copies: all 4-colourable.
  • Two twisted halves instead of one. They share the work but total about 250 points against 135 for one.
  • Other lattices. Golden lattices, decagonal lattices, finer lattices in the same field, sphere models: either too easy to colour or just more copies of the same lattice joined point to point.
  • Building from scratch with full symmetry. 874 points, far above anything reached from Parts’ graph.
  • Descents from other near-record graphs. Every one, from two 510s, a 511 and a 521, ended on the 509 plateau or one step above it.

#What I take away from it

The record stands, and after four days I understand why far better than when we started. The 509 is two pieces in balance, tied by 18 edges at the one angle that works, sitting on a small plateau with no exit in any direction we could make exact. Our 509 on Heule’s S half shows that the same height can be reached from more than one foundation.

A few things I’ll carry into other work, too:

  • Decide what counts before you search. One script, exact arithmetic, a solver you trust. It caught a few exciting “results” that turned out not to be.
  • A careful negative is a result. “Nothing below 509 exists in this universe of 283 points” is worth more than a hundred runs that simply didn’t find anything.
  • Understanding beats polishing. Our own graph stalled at 589. Studying the record taught us more in a day than the descent did in two.
  • Working with Claude felt like working with a very fast, very honest colleague. It ran the experiments, kept the books and refused to call something a result before the checker agreed. The interesting decisions about where to look next were the ones we made together.

#Where this goes next

We are not done. The lead we are following now is a different family of graphs altogether, built on seven-fold symmetry instead of the hexagonal lattice and a twist. It is early, and I’ll write about it when there is something solid to say. This post is marked as ongoing, and new findings will be added below as updates.

#Footnotes

  1. Aubrey D. N. J. de Grey, “The chromatic number of the plane is at least 5”, Geombinatorics 28 (2018). Preprint: arXiv:1804.02385. ↩

  2. Jaan Parts, “Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane”, arXiv:2010.12665 (2020). Heule’s searches: Marijn J. H. Heule, “Computing small unit-distance graphs with chromatic number 5”, arXiv:1805.12181. ↩