Theorem 11.6 — Ramsey's Theorem for s-subsets and r colours
ProvedAppliedComb.Ramsey.hypergraph_ramseyLet and be positive integers and let be a string of integers with for each . Then there exists a least positive integer such that, whenever and
is any function, there exist a colour and a subset with such that for every .
Here and is the family of -element subsets of . The case is the Pigeon Hole Principle and the case is Ramsey's Theorem for Graphs (Theorem 11.2). The book states this theorem without proof.
Formalization Note. The printed statement has three typos, read as follows: the hypothesis " for each " is read with ranging over (the string has entries); the threshold "", where is never introduced, is read as ; and "" is . The statement is IsLeast {N | 0 < N ∧ IsHypergraphRamseyBound s r h N} (hypergraphRamseyNumber s r h) with h : Fin r → ℕ; ground set Fin n, colours Fin r, both 0-based.
import Mathlib import Definitions.Def_AppliedComb_Ramsey_hypergraphRamseyNumber
namespace AppliedComb.Ramsey
/-- Theorem 11.6 (Ramsey's Theorem), Keller & Trotter p. 234, with the page's typos read as
follows: the hypothesis `h_i ≥ s` ranges over `i = 1, …, r` (the page prints `i = 1, …, s`), the
undefined threshold `n_0` is `R(s : h_1, …, h_r)` itself, and `C([n], s]` is `C([n], s)`. For
positive integers `r, s` and `h = (h_1, …, h_r)` with every `h_i ≥ s`, there is a least positive
integer `R(s : h_1, …, h_r)` such that for every `n ≥ R(s : h)` every colouring of the
`s`-subsets of `[n]` with `r` colours has, for some colour `α`, a set of `h_α` points all of whose
`s`-subsets have colour `α`; `hypergraphRamseyNumber s r h` is it. -/
theorem hypergraph_ramsey (r s : ℕ) (hr : 0 < r) (hs : 0 < s) (h : Fin r → ℕ)
(hh : ∀ i, s ≤ h i) :
IsLeast {N : ℕ | 0 < N ∧ IsHypergraphRamseyBound s r h N}
(hypergraphRamseyNumber s r h) := by sorry
end AppliedComb.Ramsey
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let and be natural numbers with and . Let assign to each colour a natural number , with for every . The statement uses two definitions.
The property holds when, for every natural number and every map
(an arbitrary -colouring of the -element subsets of ), there exist a colour and a set such that:
- , and
- every -element subset has .
The number is defined as
with the infimum of the empty set taken to be .
The theorem asserts that is the least element of the set . Concretely:
- ;
- holds;
- every positive with satisfies .
In particular, the set is asserted to be nonempty.
Degenerate cases:
- Excluded by the hypotheses: , , and any . The statement says nothing about those cases.
- : there is a single colour and every -subset receives it. The property then holds exactly when , so the statement makes (which is ).
- : the colouring colours the individual points of . The asserted is a set of points that all have colour .
- Implicit size condition: since with , the property can only hold at if for the chosen .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.