Erdős Problem #550

Let \(m_1\leq\cdots\leq m_k\) and \(n\) be sufficiently large. If \(T\) is a tree on \(n\) vertices and \(G\) is the complete multipartite graph with vertex class sizes \(m_1,\ldots,m_k\) then prove that \[R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1.\] This problem is #16 in Ramsey Theory in the graphs problem collection. Li [Li26] proved this, combining an off-Turán tree-embedding theorem with a compactness theorem for bounded-rank hypergraph obstructions. The linked formal proof states the bound for trees on an arbitrary finite vertex type and with `K_{m_1,m_2}` written as a complete multipartite graph with two parts; the statement below is the special case `V = Fin n`.