Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11.6 — Ramsey's Theorem for s-subsets and r colours

Proved
AppliedComb.Ramsey.hypergraph_ramsey

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1ramsey-theory

Let rrr and sss be positive integers and let h=(h1,h2,…,hr)h = (h_1, h_2, \dots, h_r)h=(h1​,h2​,…,hr​) be a string of integers with hi≥sh_i \ge shi​≥s for each i=1,2,…,ri = 1, 2, \dots, ri=1,2,…,r. Then there exists a least positive integer R(s:h1,h2,…,hr)R(s : h_1, h_2, \dots, h_r)R(s:h1​,h2​,…,hr​) such that, whenever n≥R(s:h1,…,hr)n \ge R(s : h_1, \dots, h_r)n≥R(s:h1​,…,hr​) and

ϕ:C([n],s)⟶[r]\phi : C([n], s) \longrightarrow [r]ϕ:C([n],s)⟶[r]

is any function, there exist a colour α∈[r]\alpha \in [r]α∈[r] and a subset Hα⊆[n]H_\alpha \subseteq [n]Hα​⊆[n] with ∣Hα∣=hα|H_\alpha| = h_\alpha∣Hα​∣=hα​ such that ϕ(S)=α\phi(S) = \alphaϕ(S)=α for every S∈C(Hα,s)S \in C(H_\alpha, s)S∈C(Hα​,s).

Here [n]={1,…,n}[n] = \{1, \dots, n\}[n]={1,…,n} and C(X,s)C(X, s)C(X,s) is the family of sss-element subsets of XXX. The case s=1s = 1s=1 is the Pigeon Hole Principle and the case s=r=2s = r = 2s=r=2 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 "hi≥sh_i \ge shi​≥s for each i=1,2,…,si = 1, 2, \dots, si=1,2,…,s" is read with iii ranging over 1,…,r1, \dots, r1,…,r (the string has rrr entries); the threshold "n≥n0n \ge n_0n≥n0​", where n0n_0n0​ is never introduced, is read as n≥R(s:h1,…,hr)n \ge R(s : h_1, \dots, h_r)n≥R(s:h1​,…,hr​); and "C([n],s]C([n], s]C([n],s]" is C([n],s)C([n], s)C([n],s). 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.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_Ramsey_hypergraphRamseyNumber
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 234, Theorem 11.6 (stated without proof; typos read as in the Formalization Note)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let rrr and sss be natural numbers with r>0r > 0r>0 and s>0s > 0s>0. Let hhh assign to each colour α∈{0,…,r−1}\alpha \in \{0,\dots,r-1\}α∈{0,…,r−1} a natural number hαh_\alphahα​, with s≤hαs \le h_\alphas≤hα​ for every α\alphaα. The statement uses two definitions.

The property HRB(s,r,h,N)\mathrm{HRB}(s,r,h,N)HRB(s,r,h,N) holds when, for every natural number n≥Nn \ge Nn≥N and every map

φ:{S⊆[n]:∣S∣=s}→{0,…,r−1},[n]={0,…,n−1},\varphi : \{S \subseteq [n] : |S| = s\} \to \{0,\dots,r-1\}, \qquad [n] = \{0,\dots,n-1\},φ:{S⊆[n]:∣S∣=s}→{0,…,r−1},[n]={0,…,n−1},

(an arbitrary rrr-colouring of the sss-element subsets of [n][n][n]), there exist a colour α\alphaα and a set H⊆[n]H \subseteq [n]H⊆[n] such that:

  • ∣H∣=hα|H| = h_\alpha∣H∣=hα​, and
  • every sss-element subset S⊆HS \subseteq HS⊆H has φ(S)=α\varphi(S) = \alphaφ(S)=α.

The number R(s:h)R(s : h)R(s:h) is defined as

R(s:h)=inf⁡{N∈N:N>0 and HRB(s,r,h,N)},R(s:h) = \inf\{N \in \mathbb{N} : N > 0 \text{ and } \mathrm{HRB}(s,r,h,N)\},R(s:h)=inf{N∈N:N>0 and HRB(s,r,h,N)},

with the infimum of the empty set taken to be 000.

The theorem asserts that R(s:h)R(s:h)R(s:h) is the least element of the set {N:N>0 and HRB(s,r,h,N)}\{N : N > 0 \text{ and } \mathrm{HRB}(s,r,h,N)\}{N:N>0 and HRB(s,r,h,N)}. Concretely:

  1. R(s:h)>0R(s:h) > 0R(s:h)>0;
  2. HRB(s,r,h,R(s:h))\mathrm{HRB}(s,r,h,R(s:h))HRB(s,r,h,R(s:h)) holds;
  3. every positive NNN with HRB(s,r,h,N)\mathrm{HRB}(s,r,h,N)HRB(s,r,h,N) satisfies R(s:h)≤NR(s:h) \le NR(s:h)≤N.

In particular, the set is asserted to be nonempty.

Degenerate cases:

  • Excluded by the hypotheses: r=0r = 0r=0, s=0s = 0s=0, and any hα<sh_\alpha < shα​<s. The statement says nothing about those cases.
  • r=1r = 1r=1: there is a single colour 000 and every sss-subset receives it. The property then holds exactly when N≥h0N \ge h_0N≥h0​, so the statement makes R(s:h)=h0R(s:h) = h_0R(s:h)=h0​ (which is ≥s≥1\ge s \ge 1≥s≥1).
  • s=1s = 1s=1: the colouring colours the individual points of [n][n][n]. The asserted HHH is a set of hαh_\alphahα​ points that all have colour α\alphaα.
  • Implicit size condition: since ∣H∣=hα|H| = h_\alpha∣H∣=hα​ with H⊆[n]H \subseteq [n]H⊆[n], the property can only hold at nnn if hα≤nh_\alpha \le nhα​≤n for the chosen α\alphaα.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by iris · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me