Erdős Problem #550
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
In Ramsey theory, the number \(R(T,G)\) is the least number of vertices such that every red-blue colouring of a complete graph contains either a red copy of the tree \(T\) or a blue copy of \(G\).
Erdős Problem #550 concerns a tree \(T\) with \(n\) vertices and a complete multipartite graph \(G\) with parts of sizes \(m_1\le\cdots\le m_k\). For sufficiently large \(n\), it asks whether
Here \(K_{m_1,m_2}\) is the complete bipartite graph with the two smallest part sizes. The proposed bound remains OPEN.
A small example
When \(k=2\), the multipartite graph \(G\) is precisely \(K_{m_1,m_2}\) and its chromatic number is two. The desired inequality becomes
which follows immediately because \(m_1\ge1\). Thus the two-part case is trivial; the substantive difficulty starts with at least three nonempty parts.
What is known
Chvátal proved the exact tree-versus-clique formula
The open multipartite estimate is more delicate because the graph on the right is complete bipartite, and the graph on the left has several independently sized parts. An estimate involving only a complete clique cannot simply be substituted for the desired bipartite Ramsey number.
GCL's current state
Source audit #1821 checks the parameter order and the trivial two-part specialization. It records the maintained problem's historical Erdős–Faudree–Rousseau–Schelp source lead, but does not claim to have located the exact original paper pages or proved the general asymptotic inequality.
What remains
Prove the stated Ramsey inequality with the correct dependence on the multipartite part sizes and a justified sufficiently-large-tree threshold, or produce a counterexample. The \(k=2\) identity and Chvátal's separate complete-clique result do not settle the genuinely multipartite case.
Sources and claim boundaries
- Erdős Problems #550: OPEN conjectural bound.
- Historical Erdős–Faudree–Rousseau–Schelp (1985) source, as cited by the maintained registry; exact primary pages not rechecked.
- GCL source return #1821: trivial boundary and audit of unverified remaining hypotheses.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1821 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: HOLD_STATUS_RECONCILIATION.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.