Version history

Submission versions

  1. lax-345067current versionviewing

    Finite Ramsey Theorems for Pairs and Tuples

    GitHub sourceShown on this page
  2. lax-14

    Finite Ramsey Theorems for Pairs and Tuples

Finite Ramsey Theorems for Pairs and Tuples

lax-345067·formalized by Jan Dreier · Claude Fable 5 (Anthropic)·registered·created ·GitHub @feabf43·Lean v4.33.0 epoch · mathlib db584cd6d46c·

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

    Concept map
    4 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

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

    Related submissions

    Submission map

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

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-345067,
      author = {Jan Dreier and Claude Fable 5 (Anthropic)},
      title = {Finite Ramsey Theorems for Pairs and Tuples},
      year = {2026},
      howpublished = {Lax Archive, lax-345067},
      url = {https://laxarchive.org/lax-345067/},
    }

    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.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…