A Resolution of Erdős Problem 550 on Tree versus Complete Multipartite Ramsey Numbers
Erdős Problem 550 asks whether, for fixed part sizes and all sufficiently large trees T, R(T, K_{m1,...,mk}) ≤ (k-1)(R(T, K_{m1,m2}) - 1) + m1.
The proof argues by contradiction from a hypothetical counterexample sequence. It uses an off-Turán tree-embedding theorem, proved by regularity and whole-edge allocation, together with Erdős–Simonovits stability to obtain stable blue reservoirs. A null-blocker compactness (rounding) theorem for bounded-rank obstruction hypergraphs then distributes the leftover vertices and yields a capacity contradiction. The full proof was formalized in Lean v4.28.0 with Mathlib, using Harmonic's Aristotle and Codex under the author's direction.
The inequality holds for all sufficiently large n-vertex trees, which resolves Erdős Problem 550. The Lean formalization comprises 134 files with no sorry or user axioms. Its axiom audit shows only propext, Classical.choice, and Quot.sound.
