We know R(4,4) is 18 and have almost no idea what R(5,5) is
On the diagonal, the list of Ramsey numbers anyone has ever computed reads: 6, 18. That is the list. R(3,3) = 6 is the party problem; R(4,4) = 18 was settled by Robert Greenwood and Andrew Gleason in 1955. Seventy years later nobody has added a third entry, and the consensus is that nobody is close.
The off-diagonal fares a little better — R(4,5) = 25 fell in 1995 after years of computation — but the pattern is the same. Every settled value required either a piece of algebra that happened to fit or a search that ran for a very long time, and both strategies expire almost immediately. R(5,5) is somewhere in 43 to 46. R(6,6) is somewhere in 102 to 165, and its lower bound has not improved since 1965.
To show R(4,4) > 17 you need a single object: a two-colouring of K₁₇ in which neither colour contains four mutually joined vertices. Greenwood and Gleason did not search for one. They wrote down the residues modulo 17, joined two of them when their difference is a perfect square, and checked that the arithmetic did the rest. The result is the Paley graph, and it is the reason the number is 18 rather than something smaller.
What makes it satisfying is that the construction is exactly optimal. R(4,4) = 18 means no colouring of K₁₈ avoids a monochromatic K₄, so 17 vertices is the ceiling and this graph reaches it. There is no better witness to look for.
5 square / 1 non-square
Not monochromatic — and it never is.
The bins at 0/6 and 6/6 are empty. That emptiness is the entire proof that R(4,4) ≥ 18.
Every edge here is decided by arithmetic: vertices are the residues mod 17, and an edge is rose when the difference between its endpoints is a perfect square mod 17. Because −1 is itself a square mod 17, the relation is symmetric; because exactly half the nonzero residues are squares, every vertex has 8 edges of each colour. Relabelling by x ↦ 3x — and 3 is not a square — exchanges the two colour classes without changing the picture, so the rose graph and the sky graph are the same graph. Greenwood and Gleason published this in 1955, and no one has needed to improve it since, because R(4,4) = 18 means nothing better exists.
Try it: Tap four vertices — any four — and read off the six edges between them. You will never get six of one colour, and the histogram beside the graph proves it by running the check over all 2,380 four-element subsets: the bins at 0/6 and 6/6 are empty. Then hit Relabel x ↦ 3x. Because 3 is not a square mod 17, the two colour classes trade places and the picture is unchanged — the graph is isomorphic to its own complement.
Plot what is known against what is provable and the shape of the subject becomes obvious. Two points, then a run of intervals, then intervals so wide they stop being informative. R(10,10) is known to lie between 798 and 9,075 — a factor of eleven, which is another way of saying we have no idea.
Two dots and six bars. The dots are R(3,3) = 6 and R(4,4) = 18, the last of which was settled in 1955 and never extended; the bars are everything else. The grey band is what the proved bounds still permit, and by k = 10 it runs from 32 to over a million. The known bracket sits inside it, pinned down by explicit constructions and by counting arguments rather than by either envelope. Hover a column for its numbers.
Try it: Toggle the envelopes on and hover along the diagonal. The known brackets sit strictly inside the band between 2^(k/2) and 4ᵏ at every k, which means neither classical bound is anywhere near tight for the values we can actually reach — and the band itself is widening far faster than the brackets are narrowing.
The definition is finite and completely explicit, so the obvious plan is to enumerate. It works exactly once. K₆ has 15 edges and therefore 32,768 two-colourings; run through all of them, find that every single one contains a monochromatic triangle, and you have proved R(3,3) = 6 with no cleverness whatsoever.
K₁₇ has 136 edges. K₄₃ has 903. The count doubles with every edge you add, and the edge count itself grows quadratically, so the search space grows like 2 raised to n squared — the fastest kind of explosion in ordinary combinatorics.
This is a real exhaustive search, not a lookup: it enumerates all 2 raised to the edge count of colourings and tests every triple in each. At K₆ that is 32,768 colourings and the answer arrives instantly; at K₇ it is 2,097,152 and you can feel it. The routine refuses to run past 24 edges, which is n = 7, because the next step up is already hopeless.
Brute force works on exactly one Ramsey number and then stops. Isomorphism reduction does not save it either: quotienting the colourings of K₄₃ by its 43! relabellings divides by roughly 1052, which removes 52 digits from a 272-digit number. Every value beyond R(4,4) has been approached with structure — algebraic constructions from below, clever counting from above — and the two ends have never met.
Try it: Run the exhaustive scan at K₅ and K₆. The first finds twelve surviving colourings; the second finds none at all, out of 32,768 — that pair of runs is a complete proof of R(3,3) = 6, executed in your browser in a few milliseconds. Then look at where the dashed line marking every atom in the universe falls on the milestone chart. It is indistinguishable from zero.
Erdős had a standard way of explaining the difference between the next two open cases, involving a hostile alien fleet and a deadline. The joke works because the two demands sound interchangeable — one number, then the number after it — and are separated by more than a thousand orders of magnitude.
Erdős liked to imagine an alien fleet arriving with a demand. Give us R(5,5) within a year, they say, or we destroy the planet. His answer was that we should drop everything — every computer, every combinatorialist — and we would probably get it. If instead they asked for R(6,6), he said, we should give up on the mathematics and attack the fleet.
The second problem is not twice the first, or a thousand times it. Its search space is larger by a factor of 101,279 — a number with more digits than the first search space has digits. The two demands sound equally reasonable and are not remotely comparable.
roughly every machine on Earth for a century
That budget covers 11.04% of the exponent, not of the work — the bar would have to reach the far end before a single percent of the colourings had been touched.
Comply. Not by enumeration — that is hopeless in both columns — but because R(5,5) has only 4 candidate values left, and the tools that narrowed it to 43–46 are the kind that finish problems. Serious opinion has long held that the answer is 43. Erdős’s point was that a year of the whole field’s attention might well be enough.
Try it: Switch between the two targets and watch the bar. R(5,5) has four candidate values left; R(6,6) has sixty-four, and its search space is larger by a factor with more digits than R(5,5)’s search space has digits. Then drag the compute budget from a supercomputer-second to every machine on Earth running since the Big Bang, and watch how little the bar moves.
Lower bounds come from constructions: algebraic ones like the Paley graph, and probabilistic ones that prove a colouring exists without producing it. Upper bounds come from counting arguments and, increasingly, from computer search over graphs rather than over colourings — the 2016 resolution of the Boolean Pythagorean triples problem produced a certificate 200 terabytes long. The asymptotic race is a different sport entirely: in 2023 the exponential base for R(k,k) finally dropped below 4, which moved nothing at all in the table above. Asymptotics and small cases are, in this subject, almost unrelated problems.