← All papers
First page of A Resolution of Erdős Problem 550 on Tree versus Complete Multipartite Ramsey Numbers

A Resolution of Erdős Problem 550 on Tree versus Complete Multipartite Ramsey Numbers

Eric Li

math.CO Jun 22, 2026 · v2
The complete proof is formalized in Lean 4 with Mathlib across 134 sorry-free files, produced with Aristotle and Codex and audited by the author.
We resolve Erdős Problem 550, originally asked as question (2) of Erdős, Faudree, Rousseau, and Schelp. Precisely, for fixed integers $k\geq 2$ and $1\leq m_1\leq \cdots \leq m_k$, we prove that, for every sufficiently large $n$ and every $n$-vertex tree $T$, $R(T,K_{m_1,\ldots,m_k}) \leq (k-1)(R(T,K_{m_1,m_2})-1)+m_1$. The proof combines an off-Turán tree-embedding theorem, proved by regularity and whole-edge allocation, with a compactness theorem for bounded-rank hypergraph obstructions. The full and unconditional proof has been formally verified in Lean.

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.