With k colours the answer explodes — and for decades nobody could say how fast
Write Rk(3) for the smallest number of vertices that forces a monochromatic triangle when the edges are painted in k colours. It is 3, then 6, then 17, and after that nobody knows a single value. The question that matters is not which number comes next — it is the shape of the sequence.
Two answers were on the table for seventy years. The constructions said the growth might be exponential, something like ck for a fixed c. The only known ceiling said it might be factorial, roughly e·k! — which is kΘ(k), a base that keeps climbing. Between ck and kk is an enormous amount of room, and neither side could be closed.
Here is the trick that produced every classical lower bound. Take a colouring with no monochromatic triangle. Replace each of its vertices by a block of five, paint the edges inside each block with two brand new colours in the pentagon-and-pentagram pattern, and leave the edges between blocks with the colours they already had. The result is five times as large, uses two more colours, and still has no monochromatic triangle.
Checking all 2,300 triples…
Each square is one edge, coloured by its class; the diagonal is blank. Every step replaces each vertex of the current colouring by a block of five and paints the edges inside those blocks with two fresh colours in the pentagon pattern. Squint at the picture and you see the previous level exactly, one zoom level out — the same matrix with the blocks standing in for its vertices. A monochromatic triangle would have to be in one of the fresh colours, and those live inside a single block where the pentagon forbids it, or in an inherited colour, and those join three different blocks that would then form a monochromatic triangle at the previous level. Neither can happen. Two more colours buy five times the vertices, and that exchange rate is exactly the problem.
Try it: Press Blow up ×5 three times: 5 vertices on 2 colours becomes 25 on 4, then 125 on 6, then 625 on 8. Each step is verified by enumerating every triple — the last one checks 40,495,000 of them and finds nothing. Watch the matrix: each level is the previous one zoomed out, with a pentagon dropped into every cell of the diagonal.
Two colours for a factor of five is a rate of √5 ≈ 2.24 vertices per colour. Starting from the sixteen-vertex three-colouring of the previous lesson does slightly better — sixteen for three colours, a rate of 2.52 — and mixing the two, or spending a spare colour to double the size, is the best anyone ever got out of products. Every one of those rates is a constant. That is what makes the lower bound exponential and nothing more.
The upper bound is embarrassingly simple, which is part of why it has never been improved in general. Pick any vertex and sort its edges by colour. With enough edges, pigeonhole hands you a large neighbourhood in a single colour — and that neighbourhood is either the source of an immediate triangle or a smaller copy of the same problem with one fewer colour. Unrolled, that gives Rk(3) ≤ ⌊e·k!⌋ + 1.
Take any vertex. Its 1,957 edges fall into 6 colour classes, and that is one more than 6 × 326, so some colour claims at least 327 of them. Inside that neighbourhood either one edge repeats the colour — a triangle at once — or the whole neighbourhood avoids it and is left as a 5-colouring of 327 vertices, which is the bound already established for R5(3) and so forces a triangle by itself.
The narrow rose block is the single extra edge that makes the pigeonhole bite. In symbols: Rk(3) ≤ k·(Rk−1(3) − 1) + 2.
The recurrence gives 1,958 at k = 6, and ⌊e·k!⌋ + 1 gives 1,958. They agree exactly — the closed form is the recurrence, not an approximation to it.
At base 3.20 the exponential leads until k = 6, and never again. The factorial is really (k/e)k — a base that grows with k — so it outruns any constant base you name.
Try it: Slide the base c up as far as it will go and watch the exponential lose anyway. The factorial is really (k/e)k: its base grows with k, so it eventually beats every fixed base, and the crossover point tells you exactly when.
At three colours the bound is exact — ⌊e·3!⌋ + 1 = 17, and R3(3) = 17. It is the last time it is right about anything.
Put the two side by side and the state of knowledge before 2026 looks like this: a floor rising by a constant factor per colour, a ceiling rising by a factor of k per colour, and no argument anywhere that favoured either.
1 × GF(16) + 1 × doubling — about 2.378 per colour, so the growth is exponential and nothing more.
One greedy neighbourhood argument, unchanged since the 1950s and still the best general ceiling anybody has.
The true value could sit anywhere across that factor, and until 2026 no argument existed that ruled out either end.
At 4 colours the value is known to lie between 51 and 62 — a much tighter window than the general bounds allow, because dedicated constructions and computer searches beat both of them at this size. The general argument only places it above 32 and at most 66.
Both bars are logarithmic. Drag k upward and watch the rose bar stretch: the lower end climbs by a constant factor per colour while the upper end climbs by a factor of k, so the range widens without limit. Deciding which end is the truth is Erdős Problem 183.
Try it: Set k = 4. The general bounds allow anything from 33 to 66, while dedicated constructions and computer searches have narrowed the truth to between 51 and 62 — better than either general argument, and available only because four colours is still small enough to attack directly. Now drag k to 20 and the two general bounds are a factor of more than 1010 apart, with nothing in the literature to fill the space.
It is tempting to think more colours should make life easier — more classes, each of them sparser, each individually further from containing a triangle. The opposite happens, for reasons that are worth naming.
the greedy argument loses a whole factor of k per colour
the best blow-up here gains 16 vertices for 3 colours, and no more
One side compounds a growing factor, the other compounds a fixed one. That is the whole shape of the problem, and no amount of cleverness about a single colour changes it.
Colourings of K17 on 3 colours. Going from 2 to 3 colours multiplies the adversary’s options by 8.9 × 1023, and every one of them is a fresh way to hide the triangle you are hunting.
A construction has to keep 3 colour classes triangle-free simultaneously, and the classes partition the same edge set. Fixing a triangle in one class means moving an edge into another, where it may close a triangle there. There is no local repair — the classes have to be designed together, which is why the successful constructions come from algebra rather than from search.
Two colours have R(3,3) = 6 to build from. Three have R(3,3,3) = 17. Four have nothing — no exact value has ever been established past three colours, so a recursion that wants Rk−1(3) as input is working from a range rather than a number, and the uncertainty compounds along with everything else.
Erdős asked whether the k-th root of Rk(3) settles down to a finite limit. If the growth is exponential, it does — the root converges to the base. If the growth is kΘ(k), it does not, because the root is roughly k/e and simply runs away. He offered $100 for a proof that the limit was finite, which tells you which way he was leaning. What happened to that question in 2026, and who answered it, is the subject of The Machine Age.