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