Finite Ramsey Theorems for Pairs and Tuples
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
This submission puts the finite Ramsey theorems for pairs and for tuples on the archive as citable, dependency-free statements: a colouring of the pairs or of the ordered tuples of a large enough finite set admits a large homogeneous subset. Mathlib states no finite Ramsey theorem at the pinned revision.
Three theorems are stated over one definition, the order type of a tuple over a linearly ordered set: the multicolour Ramsey theorem for pairs, that every colouring of the unordered pairs of a large enough finite set with k colours has a monochromatic subset of any requested size; Ramsey's theorem in the graph form the literature cites, that every large enough graph has a clique on a vertices or an independent set on b vertices; and the Erdős–Rado theorem for tuples, that every colouring of the l-tuples over a large enough linearly ordered finite set has a large subset on which the colour of a tuple depends only on its order type. All three are existential bounds over the canonical carriers , with sizes counted by ; no Ramsey number is defined, since no statement here consumes a numeric bound.
The graph form is discharged by a glue proof from the multicolour statement alone: a pair is coloured by whether it is an edge, and the two colour classes are read as a clique and as an independent set. The multicolour statement is proved by induction on the list of colours from the two-colour case, the Erdős–Szekeres neighbourhood-splitting induction; the tuple statement by Erdős–Rado chain building for strict-monotone tuples, followed by factoring an arbitrary tuple through its rank pattern and iterating over the finitely many patterns.
Concepts
- thm✓
Lax14.MulticolorRamsey - def
Lax14.OrderTypes - thm✓
Lax14.Ramsey - thm✓
Lax14.TupleRamsey
Concept map
Proofs
Proof networkview on GitHub
-
thm✓
Lax14.Ramsey
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
Cite this
@misc{lax-14,
author = {Jan Dreier and Claude Fable 5 (Anthropic)},
title = {Finite Ramsey Theorems for Pairs and Tuples},
year = {2026},
howpublished = {Lax Archive, lax-14},
url = {https://laxarchive.org/lax-14/},
}
References
- Frank P. Ramsey. On a Problem of Formal Logic. Proceedings of the London Mathematical Society 30:264–286, 1930. doi:10.1112/plms/s2-30.1.264
- Paul Erdős and Richard Rado. Combinatorial Theorems on Classifications of Subsets of a Given Set. Proceedings of the London Mathematical Society 2:417–439, 1952. doi:10.1112/plms/s3-2.1.417
- Nikolas Mählmann. Monadically Stable and Monadically Dependent Graph Classes: Characterizations and Algorithmic Meta-Theorems. Universität Bremen, 2024.
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments