A Resolution of Erdős Problem 550 on Tree versus Complete Multipartite Ramsey Numbers
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.23659
curl -X POST /api/v1/records/arxiv/2606.23659/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.23659/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'