Skip to content

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

\[ R(T,G)\le (\chi(G)-1) \bigl(R(T,K_{m_1,m_2})-1\bigr)+m_1. \]

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

\[ R(T,G)\le R(T,G)-1+m_1, \]

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

\[ R(T,K_m)=(m-1)(n-1)+1. \]

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.

Back to catalogue · Compendium introduction