Proof of `Ramsey's theorem for colourings of pairs`

groundedproofs/Lax14Proofs/MulticolorRamsey.lean · lax-14

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Every colouring of the unordered pairs of a large enough finite set with kk colours admits a monochromatic subset of size ss: the multicolour Ramsey theorem for pairs, over the canonical carriers FinnFin n and with no hypothesis on the number of colours.

Proof strategy

The mathematical content is the ported Lax14Proofs.PairRamsey.multicolorramseyLax14Proofs.PairRamsey.multicolor_ramsey, which asks for a list of requested sizes, one per colour, and produces a FinsetFinset monochromatic in the colour whose entry it meets. That statement is proved by induction on the list of colours from the two-colour graph form Lax14Proofs.PairRamsey.ramseyLax14Proofs.PairRamsey.ramsey (Erdős–Szekeres neighbourhood splitting): the first colour is turned into a graph, a clique in it is monochromatic of the first colour, and an independent set carries a colouring by the remaining colours to which the induction hypothesis applies.

The bridge to the submitted statement instantiates the list as List.replicateksList.replicate k s, so that all colours request the same size ss, and transports along List.lengthreplicate:(List.replicateks).length=kList.length_replicate : (List.replicate k s).length = k, precomposing the given colouring with Fin.castFin.cast in one direction and casting the returned colour index back in the other. The carrier is FinnFin n, whose Fintype.cardFintype.card is nn, and the returned FinsetFinset is coerced to a SetSet, its cardinality translated by Set.ncardcoefinsetSet.ncard_coe_finset.

The submitted statement carries no positivity hypothesis on the number of colours, whereas the ported one needs a nonempty list. The case k=0k = 0 is therefore split off first and closed outright: with N:=1N := 1 the carrier FinnFin n is nonempty, so the assumed colouring produces an element of Fin0Fin 0, which is absurd.

Attribution

The proof is ported from the proof package of the submission Monadic dependence and neighborhood complexity (Lax5Proofs/Ramsey.leanLax5Proofs/Ramsey.lean), where it appears as Theorems 3.7 and 3.8 of the source lecture notes. The theorem is due to Ramsey, On a problem of formal logic (Proc. London Math. Soc. 1930); the two-colour induction used here is the Erdős–Szekeres argument.