Sixteen vertices, three colours, no monochromatic triangle — and one exceptional graph behind it
Two colours force a monochromatic triangle at six vertices. Add a third colour and the threshold does not creep up to seven or eight — it goes to seventeen. Sixteen vertices can be three-coloured with no triangle in any single colour; seventeen cannot, no matter what you try.
That number is written R(3,3,3), and Robert Greenwood and Andrew Gleason determined it in 1955. It remains the only non-trivial multicolour triangle Ramsey number anybody has ever pinned down. Seventy years of computing power later, the four-colour version is still known only to lie somewhere between 51 and 62.
Here is the witness. Sixteen vertices, 120 edges, split into three classes of exactly 40 — and not one of those classes contains a triangle. Each class is 5-regular, and all three are the same graph: the Clebsch graph, an exceptional object that turns up repeatedly in extremal combinatorics and is doing all the work here.
Vertices are the sixteen elements of the field GF(16). The edge between x and y takes its colour from which of three sets contains x − y — and in this field subtracting is the same as adding, so there is no direction to worry about.
generator 2 · cosets {1,8,10,12,15} {2,3,7,11,13} {4,5,6,9,14}
Hover a vertex to isolate its edges. Turn colours off one at a time: each class on its own is 5-regular with 40 edges and no triangle anywhere — the Clebsch graph. Three copies of it tile all 120 edges of the complete graph, which is why sixteen vertices can be three-coloured and seventeen cannot.
Try it: Switch two colours off and look at what is left. Every vertex has exactly five edges, the graph looks unremarkable, and yet no three of those vertices are mutually joined. Then switch to the grid layout, where the vertices sit at the sixteen four-bit patterns and the arithmetic behind the arrangement starts to show through.
Nobody found that partition by searching. It falls out of the field with sixteen elements. GF(16) has fifteen nonzero elements under multiplication, fifteen factors as three times five, and a cyclic group of order fifteen has exactly one subgroup of order five. That subgroup has three cosets, the cosets have five elements each, and the three cosets are the three colours.
GF(16) is the set of polynomials in x of degree at most three with coefficients 0 or 1, added coefficientwise and multiplied modulo x4 + x + 1. Sixteen of them, one for each four-bit pattern — so the elements are just the numbers 0 to 15 wearing a different hat.
Addition is bitwise exclusive-or, so every element is its own negative: x + x = 0. That is why subtraction never needs a sign, and why the colouring below has no direction to it.
Try it: Walk the five steps. The only input is the polynomial x⁴ + x + 1; everything after that — the generator, the subgroup, the cosets, the colouring — is forced. On the last step, click cells in the difference table to see which coset decides each edge.
Sixteen works. The whole content of R(3,3,3) = 17 is that seventeen does not — and since the sixteen-vertex colouring above is essentially the only one that works, the honest test is to keep it and try to attach a seventeenth vertex without damage. You get sixteen new edges and complete freedom over their colours.
40 monochromatic triangles
Every triangle listed uses the new vertex, because the sixteen fixed edges contain none on their own: 0–1–17 all rose, 0–8–17 all rose, 0–10–17 all rose, …
Sixteen spokes into three colours means one colour is used at least six times — that is the pigeonhole step, and you can watch the counter above refuse to go below six. Now look at those six or more vertices inside the colour class they share. That class is the Clebsch graph, and the largest set of Clebsch vertices with no edge between them has exactly five members. Six vertices therefore contain an edge of that colour, and that edge closes a triangle with the new vertex.
Click any spoke to cycle it through rose, sky and amber. The search button walks all 3¹⁶ assignments with pruning and returns the genuine optimum: 5 triangles, never zero.
Try it: Colour the sixteen spokes however you like, then press Find the best possible. The search covers every one of the 3¹⁶ assignments and the answer is five monochromatic triangles. Not one. Five. The seventeenth vertex has nowhere to go.
The reason is two short observations stacked together. Sixteen spokes into three colours puts at least six spokes in one colour — pigeonhole. And the largest collection of vertices with no edge between them inside a single Clebsch graph has five members, so any six of them contain an edge of that colour. That edge and the new vertex close a triangle. The argument needs no computer, and the computer agrees.
Three colours were settled in 1955. Four have never been settled, nor five, nor any number after that. The classical ceiling ⌊e·k!⌋ + 1 sits exactly on the answer at k = 3, giving 17 on the nose — and then it drifts, permitting 66 at four colours when the truth is at most 62, and 1,958 at six colours when the best construction reaches only 537.
Greenwood and Gleason, 1955 — the only non-trivial value ever determined
Nothing. This value is pinned exactly, and at k = 3 the classical ceiling lands on it — ⌊e·3!⌋ + 1 is 17, and R3(3) is 17. That coincidence is the last time the bound is tight.
Hover or tap a column to move between them.
Try it: Move along the columns. The scale is logarithmic, so the shaded bars are not as small as they look — the six-colour bar spans a factor of more than three, and that is the best anyone can say.
The three-colour case is where the multicolour problem shows both its faces at once. From below, a construction can be exquisite and arithmetic and still only reach sixteen vertices. From above, a bound as crude as a greedy neighbourhood count can be exactly right. Those two things pull apart immediately afterwards, and how far apart they get is the subject of Many Colours.