Finite Ramsey Theorems for Pairs and Tuples

lax-14·formalized by Jan Dreier·Claude Fable 5 (Anthropic)·registered·created 2026-08-02·GitHub @38629a6·Lean v4.30.0 epoch · mathlib c5ea00351c28

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    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 FinnFin n, with sizes counted by Set.ncardSet.ncard; 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✓proven claimdefdefinition

    Concept map

    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    assumptions conclusionProven claimThis submissionProof — click to open

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    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

    1. 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
    2. 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
    3. 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

    Loading discussion…