Classification of finite Euclidean Ramsey configurations

The explanation

Color every point of space with one of three colors. Must some pair of points exactly one unit apart share a color? In ordinary three-dimensional space, yes. Take the four corners of a regular tetrahedron with all six edges one unit long. Four corners and three colors means two corners match, and they are one unit apart. With more colors, you just move to more dimensions, where larger such shapes fit.

A finite set of points is called Ramsey when this always works. For any number of colors, some high enough dimension forces a copy of the set in a single colorSource 1. The copy must be congruent: every distance stays exactly the same, at the original scale. The coloring can be completely arbitrary, with no smoothness of any kindSource 2. So the two-point set above is Ramsey.

Not every set is. Three points evenly spaced on a line are not Ramsey. In 1973, Erdős, Graham, Montgomery, Rothschild, Spencer and Straus started this subject. They proved that every Ramsey set must lie on a sphereSource 3. Three points on a line lie on no sphere. Graham later conjectured that lying on a sphere is enoughSource 4. Frankl and Rödl proved that every simplex is Ramsey, a simplex being a triangle, tetrahedron or higher versionSource 5.

A second guess came from Leader, Russell and Walters in 2012. A set is transitive when its symmetries can move any of its points to any other, like a regular polygon's corners. They conjectured that a set is Ramsey exactly when it fits inside some finite transitive setSource 6. Then, recently, Pálvölgyi found seven points on a circle that are not RamseySource 7. That disproved Graham's conjecture.

This paper proves an exact test for every finite setSource 8. The test is an algebraic condition on the coordinates of the points. Lying on a sphere means the points satisfy one equation. The paper’s condition asks for a stronger form of that equation, one that keeps two copies of the coordinates apart. That stronger form is exactly what separates spheres from Ramsey setsSource 9. The test works with exact algebra. It is not a recipe for deciding from rounded decimal coordinatesSource 10.

The test settles concrete cases. Every set that fits inside a finite transitive set passesSource 11. So does every set of at most five points on a circleSource 12. That includes every four-sided shape whose corners lie on a circle. In 2011, Leader, Russell and Walters had found such kite shapes that fit in no finite transitive set. Those kites are Ramsey, so their 2012 conjecture failsSource 13.

The single difficulty was getting an exact copy from an arbitrary coloring. One direction is easier. When the condition fails, algebra builds a coloring that avoids the set in every dimensionSource 14. The other direction is hard. A wild coloring has no continuity, so a copy that is almost right is worth nothingSource 15. The proof turns the algebra into two lists of numbers with matching distances. Then it uses tools from infinite combinatorics to land a copy at exactly the right scale.

How sure is this? A computer proof checker called Lean has checked formal versions of the main results. They include the exact test, the fact that every Ramsey set lies on a sphere, and the transitive and five-point cases. They also include two sets that fail: a twelve-point set and a nine-point set on a circle. No specialist review of the paper has been published.

What it doesn't show. This does not give a way to run the test from rounded decimal coordinates.