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

Abstract

We resolve Erdős Problem 550, originally asked as question (2) of Erdős, Faudree, Rousseau, and Schelp. Precisely, for fixed integers $k\ge 2$ and $1\le m_1\le \cdots \le m_k$, we prove that, for every sufficiently large $n$ and every $n$-vertex tree $T$, $R(T,K_{m_1,\dots ,m_k})\le (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.

V2: The proof has been formally verified in Lean. 26 pages