Lax14.MulticolorRamsey

Ramsey's theorem for colourings of pairs

concepts/Lax14/MulticolorRamsey.lean · lax-14

proven

Loading review…

Sign in with ORCID

Community review

Flags

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

No flags have been submitted.

    Community review

    Flag this concept

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

    No source line selected.

    Concept map

    Proven claimThis concept

    Evidence

    Each proof establishes this claim relative to its assumptions.

    Theorem

    For every number of colours k and every size s there is an N such that for every colouring of the unordered pairs of an N-element set with k colours there is a monochromatic subset of size s: a set of s elements all of whose pairs receive one and the same colour. This is Ramsey's theorem for pairs in its multicolour form; the number of colours and the requested size are arbitrary and the bound N depends only on them.

    Lean source view on GitHub

    1import Mathlib.Data.Sym.Sym2
    2import Mathlib.Data.Set.Card
    3
    4/-!
    5---
    6title: Ramsey's theorem for colourings of pairs
    7type: theorem
    8---
    9For every number of colours *k* and every size *s* there is an *N* such
    10that for every colouring of the unordered pairs of an *N*-element set with
    11*k* colours there is a monochromatic subset of size *s*: a set of *s*
    12elements all of whose pairs receive one and the same colour. This is
    13Ramsey's theorem for pairs in its multicolour form; the number of colours
    14and the requested size are arbitrary and the bound *N* depends only on
    15them.
    16
    17# Formalization notes
    18
    19The colouring is a plain function on `Sym2 (Fin n)`, mathlib's type of
    20unordered pairs; no notion of colouring is introduced. Colourings assign a
    21colour to the degenerate pairs `s(u, u)` as well, and the conclusion
    22ignores them — `Set.Pairwise` constrains distinct elements only — so
    23colourings of the edges of the complete graph are exactly the functions
    24considered here, restricted along an inclusion that changes nothing.
    25
    26Sizes are stated as "at least": a monochromatic set of size at least *s*
    27contains one of size exactly *s*, and the stated form is what every
    28application uses. All statements of this submission range over the
    29canonical carriers `Fin n` and over all `n` beyond the bound, so the
    30theorem applies to a set of any size by transport along a bijection.
    31
    32The Ramsey number itself is deliberately not defined. The archive's
    33convention for a numeric parameter would be `sInf {N | …}`, but no
    34statement of this submission consumes a numeric bound, so such a
    35definition would be endorsement surface that nothing uses; the existential
    36carries the whole content.
    37
    38No hypothesis is placed on the number of colours: for `k = 0` there is no
    39colouring of the pairs of a nonempty set at all, so the statement holds
    40vacuously with `N = 1`.
    41-/
    42
    43namespace Lax14.MulticolorRamsey
    44
    45/-- Ramsey's theorem for pairs: every `k`-colouring of the unordered pairs
    46of a large enough finite set has a monochromatic subset of size `s`. -/
    47axiom exists_monochromatic_set (k s : ℕ) :
    48 ∃ N : ℕ, ∀ (n : ℕ) (c : Sym2 (Fin n) → Fin k), N ≤ n →
    49 ∃ (i : Fin k) (S : Set (Fin n)), s ≤ S.ncard ∧
    50 S.Pairwise fun u v => c s(u, v) = i
    51
    52end Lax14.MulticolorRamsey
    53
    Show Proof

    Formalization notes

    The colouring is a plain function on Sym2(Finn)Sym2 (Fin n), mathlib's type of unordered pairs; no notion of colouring is introduced. Colourings assign a colour to the degenerate pairs s(u,u)s(u, u) as well, and the conclusion ignores them — Set.PairwiseSet.Pairwise constrains distinct elements only — so colourings of the edges of the complete graph are exactly the functions considered here, restricted along an inclusion that changes nothing.

    Sizes are stated as "at least": a monochromatic set of size at least s contains one of size exactly s, and the stated form is what every application uses. All statements of this submission range over the canonical carriers FinnFin n and over all nn beyond the bound, so the theorem applies to a set of any size by transport along a bijection.

    The Ramsey number itself is deliberately not defined. The archive's convention for a numeric parameter would be sInfNsInf {N | …}, but no statement of this submission consumes a numeric bound, so such a definition would be endorsement surface that nothing uses; the existential carries the whole content.

    No hypothesis is placed on the number of colours: for k=0k = 0 there is no colouring of the pairs of a nonempty set at all, so the statement holds vacuously with N=1N = 1.

    Builds on

    none

    Used by

    none

    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…