Alphabeta Math

Ramsey Theory

About this page
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 15 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 15 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Combinatorics
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

Finite colourings of k-element subsets, monochromatic sets, and the arrow notations N→(s,t)² and N→(r)ᵏ_c

Lemma

If m→(s-1,t)² and n→(s,t-1)², then m+n→(s,t)² for s,t≥2

Theorem

Finite graph Ramsey theorem: C(s+t-2, s-1)→(s,t)² for all positive s,t

Definition

The off-diagonal Ramsey number R(s,t) as the least N with N→(s,t)², for positive s,t

Corollary

R(s,t)≤ R(s-1,t)+R(s,t-1) for s,t≥2, and R(k,k)leC(2k-2, k-1)≤2²ᵏ⁻²

Theorem

The Ramsey number R(3,3)=6

Theorem

Erdős's finite counting bound R(k,k)>2^k/2 for every k≥3

Theorem

For positive k,c,r there is an N such that every c-colouring of [N]ᵏ has a monochromatic r-element set

Definition

The uniform Ramsey number Rₖ(r;c) as the least finite witness for c colours on k-element subsets

Definition

Rooted trees of finite sequences, levels, branches, and finite branching, with ordered finite successor sets

Theorem

König's infinity lemma: an ordered finitely branching tree with a node at every level has an infinite branch, in ZF

Lemma

Every finite colouring of ℕ has an infinite colour class, in ZF

Theorem

Infinite Ramsey theorem on ℕ: every finite colouring of [ℕ]ᵏ has an infinite monochromatic set, in ZF

Corollary

Infinite Ramsey holds for every set equipped with an injection from ℕ

Corollary

The finite uniform Ramsey theorem follows a second time from the infinite theorem by a finitely branching tree of bad finite colourings

Theorem

Canonical Ramsey theorem for pairs: on an infinite subset a colouring is constant, injective, left-dependent, or right-dependent

Lemma

Finite colour focussing extends equally coloured progressions to a longer monochromatic arithmetic progression

Theorem

Van der Waerden's theorem, strengthened so the progression and its common difference have one colour

Definition

The van der Waerden number W(k,c) as the least interval length forcing a monochromatic k-term arithmetic progression

Theorem

Schur's theorem: every finite colouring of a sufficiently long positive initial interval {1,…,N} has positive monochromatic x,y,z with x+y=z

Definition

The Schur number S(c) as the largest N for which {1,…,N} has a c-colouring with no positive monochromatic solution of x+y=z

Sources