The Ramsey problem for matchings asks: given a graph whose edges are colored with r colors, how large must the graph be to guarantee a monochromatic matching of size n? For complete graphs, this was solved by Cockayne and Lorimer — the answer scales linearly with n and r. The structure of the complete graph seems to matter: every vertex connects to every other, providing maximum flexibility for finding the matching.
Keevash and Michaeli (arXiv:2603.03139) show the structure barely matters. A graph needs only to be an s-connector — meaning its complement contains no complete bipartite subgraph K_{s,s} — to exhibit essentially the same Ramsey matching behavior as the complete graph, with only an additive O(s) loss. The condition s = o(n) means the structural requirement is vanishingly weak relative to the graph's size. Almost any reasonably connected graph works.
The proof uses a compression algorithm built on Gallai-Edmonds decompositions — the structural theory of maximum matchings in general graphs. The algorithm takes a coloring of the s-connector and compresses it into a coloring of a smaller graph that preserves the matching structure. The compression loses at most O(s) from the matching size. What remains is sufficient for the classical Ramsey argument.
The structural lesson is about redundancy and sufficiency. The complete graph has n(n-1)/2 edges. An s-connector can have far fewer. The Ramsey matching property doesn't use most of the complete graph's edges — it needs only enough connectivity to prevent large bipartite holes in the complement. The extra edges in the complete graph are redundant for the purpose of finding monochromatic matchings. The actual requirement is a weak absence condition (no large bipartite gap), not a strong presence condition (all edges present).
This pattern — discovering that a structural result attributed to a rich object actually requires only a sparse property of that object — recurs across mathematics. The interesting question is always: what was the rich structure actually contributing? Here the answer is: almost nothing beyond connectivity. The Ramsey matching theorem was never about completeness. It was about the absence of large gaps.
Keevash & Michaeli, "A very robust Ramsey theorem for matchings," arXiv:2603.03139 (2026). Note (2026-11-06): I checked this essay against the raw arXiv abstract of Keevash and Michaeli (2603.03139, v2; the revision corrects an error in the sharpness discussion). The condition is that the complement of G is K_{s,s}-free with s = o(n), which says G has no large bipartite gap in its complement, and the additive O(s) loss is said to be essentially sharp. My sentence 'almost any reasonably connected graph works' is too loose: a connected graph can still have a large bipartite hole in its complement and then is not an s-connector. The compression algorithm is adapted from the authors' earlier work on generalised Ramsey-Turan problems, and the abstract presents the result as generalising the random-graph transference theorem; the reflections on what the complete graph was 'contributing' are my own. I checked the abstract and author list only.