A Resolution of Erd\H{o}s Problem 550 on Tree versus Complete Multipartite Ramsey Numbers

Eric Li (Trinity College; University of Cambridge)

REVIEW 1 major objections 6 minor 14 references

A Resolution of Erd\H{o}s Problem 550 on Tree versus Complete Multipartite Ramsey Numbers

T0 review · 1 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that for every fixed k and fixed part sizes m1≤...≤mk, every sufficiently large tree T satisfies R(T, K_{m1,...,mk}) ≤ (k-1)(R(T, K_{m1,m2})-1)+m1, thereby resolving a 1989 problem in Ramsey theory.

desk verdict The proof of the central stability step is built on a color mismatch in Theorem 3.2/Cor 3.3 that makes Eq. (25) unsupported as printed, though the intended fix looks recoverable and the overall architecture is genuinely promising. read the letter →

arxiv 2606.23659 v2 pith:SYC6YKEF submitted 2026-06-22 math.CO

Eric Li (Trinity College , University of Cambridge) This is my paper · ORCID

classification math.CO MSC 05C5505C3505C0505D10

keywords Ramseynumbertreecompletemultipartitegraphoff-Turánembeddingstabilityblockerhypergraphcompactnessregularitylemma

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper settles a long-standing open problem in Ramsey theory: for any fixed complete multipartite graph with k parts of fixed sizes, and for all sufficiently large trees, the Ramsey number of the tree against that multipartite graph is bounded above by (k-1) times the Ramsey number of the tree against the two-partite graph on the two smallest parts, plus the size of the smallest part. Together with the classical lower bound, this pins the Ramsey number to within an additive error that is sublinear in the tree size, uniformly over all trees. The proof introduces two new tools: an off-Turán tree-embedding theorem and a compactness theorem for bounded-rank blocker hypergraphs. The result is significant because it removes all structural restrictions on the tree and gives a quantitative form of 'tree Ramsey goodness' for multipartite graphs.

What carries the argument

The argument rests on two new tools. First, an off-Turán tree-embedding theorem: if a graph on N vertices contains no copy of a fixed (q+1)-chromatic graph F and has at least (N choose 2) - t_q(N) + δN^2 edges, then it contains every sufficiently large tree T; this is proved via a graph regularity lemma and a local regular-matching embedding lemma. Second, a null-blocker compactness theorem for finite hypergraphs of bounded rank: under approximate conditions that every a-set is blocked by some coordinate and every edge is blocked by another coordinate, one can delete at most a-1 vertices and partition the rest into q independent sets. The proof introduces shadow hypergraphs on a limiting seq

What would settle it

Find a graph G on N vertices that contains no copy of a fixed (q+1)-chromatic graph F and satisfies e(G) ≥ (N choose 2) - t_q(N) + δN^2 for some fixed δ>0, yet does not contain some arbitrarily large tree T. Alternatively, for a specific instance such as k=3 and m1=m2=m3=2, compute R(P_n, K_{2,2,2}) for large n; if it exceeds 2(R(P_n, K_{2,2})-1)+2, the theorem is false.

Watch

Extended reading notes

Core claim

The central claim is an upper bound on the Ramsey number of an arbitrary large tree against a fixed complete multipartite graph: R(T, K_{m1,...,mk}) ≤ (k-1)(R(T, K_{m1,m2}) - 1) + m1, where m1 ≤ m2 are the two smallest part sizes. Equivalently, the excess over the canonical lower bound (k-1)(n-1)+m1 is controlled by the excess in the two-partite Ramsey number of the two smallest parts, which is n+o(n) uniformly. The proof shows that in any hypothetical counterexample, the red graph (which avoids the multipartite graph) must have density at least that of the extremal q-partite graph, up to lower-order error; otherwise a new off-Turán embedding theorem would force the tree into the blue graph.

Load-bearing premise

The proof depends on an off-Turán tree-embedding theorem whose printed statement has an inconsistent color convention between the theorem and its corollary; if the intended correction (that the high-density graph must be T-free with an F-free complement) fails, the near-Turán density step and the final counting contradiction collapse.

Editorial extensions

If this is right

For every fixed k and part sizes, the Ramsey number R(T, K_{m1,...,mk}) is asymptotically (k-1)n + m1, uniformly over all n-vertex trees, because the bipartite Ramsey number R(T, K_{m1,m2}) equals n+o(n).
The result establishes a uniform 'tree Ramsey goodness' for complete multipartite graphs with no bounded-degree or other structural assumption on the tree.
The off-Turán embedding theorem is a standalone extremal statement: any sufficiently large tree appears in the complement of any graph that avoids a fixed (q+1)-chromatic graph and has below-Turán edge count.
The null-blocker compactness theorem is an abstract rounding mechanism that could apply to other Ramsey-type problems where finite obstructions must be converted into a partition of a large vertex set.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof strategy suggests the upper bound may extend to other classes of sparse graphs beyond trees, provided an analogous prescribed-root embedding lemma holds for that class.
The compactness theorem could be used as a general recipe for proving existence of Ramsey-good partitions without explicit construction, by extracting a limit of near-counterexamples and rounding via shadow hypergraphs.
A concrete testable extension is to check whether the bound is tight for stars or paths for small k and small part sizes; for instance, for k=3 and m1=m2=m3=2, the bound becomes 2(R(T, K_{2,2})-1)+2, and computing small cases would reveal whether the error term is necessary.
If the off-Turán embedding theorem can be reformulated to avoid the color-convention inconsistency, the near-Turán density step would follow more directly and the proof would become more modular.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper has a real shot at resolving Erdős Problem 550, and the architecture is serious: a uniform EFRS asymptotic, an off-Turán embedding theorem, stability into reservoirs, blocker hypergraphs, and a compactness-and-rounding theorem. Theorem 1.1 is a genuine advance if it holds, and the null-blocker compactness result is interesting on its own terms. The proof is detailed, and the high-level logic is coherent.

But there is a load-bearing presentation error that, as printed, breaks the argument. Theorem 3.2 states that if the dense graph G_b is F-free and has many edges, then T embeds into G_b. The proof, however, actually uses F-freeness of the complement of G_b: the independent-set step finds a red copy of F in the complement, contradicting the complement being F-free. The proof's own language ("red copy in G_b") exposes the mismatch. Corollary 3.3 then asserts "G_r := G_b", which is self-contradictory; the intended corollary should say that if G_b is T-free and its complement is F-free, then the complement has near-Turán density. As written, Eq. (25) does not follow from the stated theorem, and the stability stage that follows rests on an unproved premise.

The stress-test is right about the printed version, but it does not kill the paper: the proof of Theorem 3.2 appears to prove the corrected statement (dense graph whose complement is F-free contains T), and that corrected statement is exactly what the Ramsey application needs. The fix looks mechanical — swap the F-free hypothesis to the complement in the theorem and corollary, and clean up the color terminology. That said, until this is done, the paper is not correct as written, and a referee should check the corrected theorem carefully because the entire stability argument depends on it.

Two smaller issues: the abstract claims a full Lean formalization, but no artifact is provided; and the compactness proof is intricate enough that the referee should verify the shadow-hypergraph construction in detail.

My take: this deserves a serious referee, not a desk reject. The central idea is credible and the problem is important. I would send it to a strong referee with instructions to focus on the corrected off-Turán statement and the compactness theorem, and to require the authors to rewrite Theorem 3.2 and Corollary 3.3 unambiguously. Once the color convention is fixed, the paper may well be right.

Referee Report

1 major / 6 minor

Summary. The paper proves Theorem 1.1: for fixed k≥2 and 1≤m1≤...≤mk, every sufficiently large n-vertex tree T satisfies R(T,K_{m1,...,mk}) ≤ (k-1)(R(T,K_{m1,m2})-1)+m1, resolving Erdős Problem 550. The proof architecture is: a uniformity result of Erdős–Faudree–Rousseau–Schelp, a new off-Turán tree-embedding theorem (Thm 3.2) proved via the Hladký–Piguet regularity lemma, a stability step yielding clean reservoirs (Lemma 6.1), profile and blocker hypergraph arguments, and a compactness/rounding theorem for bounded-rank hypergraph obstructions (Thm 5.2). The final step compares the reservoir sizes with the two-part Ramsey number. The abstract also claims a Lean formal verification.

Significance. If the proof is correct, it resolves a long-standing open problem and gives a sharp upper bound matching Burr's lower bound up to an excess term controlled by the bipartite Ramsey number. The compactness theorem for null-blocker hypergraphs is a novel tool that may be of independent interest. The paper is ambitious and largely coherent; however, the printed version contains a load-bearing color mismatch in the off-Turán theorem that must be corrected before the argument is valid.

major comments (1)

[Theorem 3.2, Corollary 3.3, §6 Eq. (25)] As printed, Theorem 3.2 assumes the high-density graph G_b is F-free, but its proof derives a red copy of F in G_b (i.e., in the complement), contradicting only the F-freeness of the complement. In the Ramsey application (§6), the F-free graph is the red graph G_r, which is the complement of the blue T-free graph G_b. Corollary 3.3's identification G_r:=G_b is therefore impossible in context. Consequently, Eq. (25) does not follow: the counterexample provides no graph that is simultaneously T-free and F-free. The intended statement is obtained by replacing 'F ⊈ G_b' with 'F ⊈ \overline{G_b}' in Theorem 3.2 and setting G_r:=\overline{G_b} in Corollary 3.3; the proof of Theorem 3.2 already uses this convention. This correction is load-bearing for Lemma 6.1 and all subsequent sections.

minor comments (6)

[Lemma 4.3] The text refers to 'the upper-capacity hypothesis of Theorem 4.2'; the correct reference is Lemma 4.2.
[Section 5, cross-references] Lemma 5.6 and the proof of Theorem 5.2 refer to 'Theorem 5.3', 'Theorem 5.4', and 'Theorem 5.5'; these are Lemmas 5.3–5.5.
[Abstract] The claim of a Lean formal verification is not substantiated in the text; no formalization files or precise statement of the verified theorem are provided, and the printed color mismatch makes the claim difficult to assess. Please clarify or qualify.
[Section 6, Eq. (32)] The application of Lemma 4.3 is terse; it uses the contrapositive with d_{G_b}(x,W_i)=|W_i|-d_{G_r}(x,W_i). This step should be spelled out to avoid confusion.
[Theorem 3.2 proof] After the intended color correction, the phrase 'Some choice therefore gives a red copy of F in G_b' should be rephrased to clarify that 'red' means a copy in the complement of G_b.
[Section 6, first paragraph] The sentence 'By interchanging the two colors in the hypothetical counterexamples if necessary' is unnecessary and confusing in context; a counterexample to the stated theorem already has no red F and no blue T.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof reduces the k-partite bound to the two-part Ramsey number and proves its auxiliary theorems from scratch or from independent prior work.

full rationale

The paper's derivation chain is not circular. The main theorem upper-bounds R(T,K_{m1,...,mk}) using the two-part Ramsey number r=R(T,K_{m1,m2}) as an external input, not as the target conclusion; the counterexample assumption is used to derive a contradiction, not to prove the bound. The supporting components are independent: Proposition 2.1 is the EFRS uniform asymptotic, Theorem 3.2 is proved in-paper from Szemerédi regularity and the Hladký–Piguet lemma, and the null-blocker compactness theorem (Theorem 5.2) is proved from scratch in Section 5 with no dependence on the Ramsey theorem being proved. There are no self-citations by the present author, no fitted parameters renamed as predictions, and no uniqueness or ansatz imported from the author's prior work. The only noticeable defect is a color-consistency slip in Corollary 3.3 ('G_r := G_b') and the correspondingly unsupported derivation of Eq. (25), but that is a correctness or proof-gap concern, not a circular reduction of the conclusion to its hypotheses. Accordingly the honest circularity finding is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No parameters are fitted to data. The proof imports standard external results (regularity, stability, KST, EFRS asymptotic, Hladký–Piguet) and adds no new primitive entities beyond proof constructions such as shadow hypergraphs, which are internal mathematical objects.

assumptions (7)

standard math Szemerédi regularity lemma, in the per-cluster form of Hladký–Piguet
Used in the proof of Theorem 3.2 to produce the reduced graph Q and the cluster decomposition.
standard math Erdős–Simonovits stability theorem
Used in Lemma 6.1 to obtain a near-equitable partition of the red graph in a hypothetical counterexample.
standard math Kővári–Sós–Turán theorem
Used in Lemma 6.1 to bound the number of red edges inside each reservoir.
standard math EFRS uniform asymptotic (Prop 2.1)
Gives r = R(T,K_{a,b}) = n + o(n) uniformly over n-vertex trees; essential for N = qn + o(n) and for the quantitative form of the theorem.
standard math Hladký–Piguet local regular-matching lemma and existence of τ-fine partitions
Used as the source embedding lemma in Theorem 3.2; the paper gives a detailed dictionary to their Lemma 5.13.
standard math Turán's theorem
Used in Theorem 3.2 to find a clique in the reduced graph when its independence number is large.
standard math Kolmogorov extension theorem and Borel–Cantelli lemmas
Used in the compactness and rounding theorems (Theorems 5.1–5.4) for finite-dimensional limits and almost-sure events.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Resolution of Erd\H{o}s Problem 550 on Tree versus Complete Multipartite Ramsey Numbers." pith.science (2026). https://pith.science/paper/SYC6YKEF

@misc{pith2026260623659,
  author       = {Pith},
  title        = {Pith review of: A Resolution of Erd\Hos Problem 550 on Tree versus Complete Multipartite Ramsey Numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SYC6YKEF}},
  note         = {Machine review of arXiv:2606.23659}
}

abstract

We resolve Erd\H{o}s Problem 550, originally asked as question (2) of Erd\H{o}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\'an 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.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 7 canonical work pages

[1]

Aharoni, R

R. Aharoni, R. Holzman, D. Howard, and P. Sprüssel, Cooperative colorings and independent systems of representatives,Electron. J. Combin.22(2015), Paper P2.27, doi:10.37236/2488

work page doi:10.37236/2488 2015
[2]

X. Bai, B. Li, W. Liu, and X. Zhang, Cooperative colorings of hypergraphs, arXiv:2408.03727, 2024

arXiv 2024
[3]

Balla, A

I. Balla, A. Pokrovskiy, and B. Sudakov, Ramsey goodness of bounded degree trees,Combin. Probab. Comput. 27(2018), 289–309, doi:10.1017/S0963548317000554

work page doi:10.1017/s0963548317000554 2018
[4]

S. A. Burr, Ramsey numbers involving graphs with long suspended paths,J. London Math. Soc.(2)24(1981), 405–413, doi:10.1112/jlms/s2-24.3.405

work page doi:10.1112/jlms/s2-24.3.405 1981
[5]

Chvátal, Tree-complete graph Ramsey numbers,J

V. Chvátal, Tree-complete graph Ramsey numbers,J. Graph Theory1(1977), 93, doi:10.1002/jgt.3190010118

work page doi:10.1002/jgt.3190010118 1977
[6]

Erdős, R

P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Multipartite graph–sparse graph Ramsey numbers, Combinatorica5(1985), 311–318, doi:10.1007/BF02579245

work page doi:10.1007/bf02579245 1985
[7]

Erdős, R

P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Multipartite graph–tree Ramsey numbers, in Graph Theory and Its Applications: East and West, Ann. New York Acad. Sci.576(1989), 146–154

1989
[8]

T. F. Bloom, Erdős Problem 550,https://www.erdosproblems.com/550, accessed 22 June 2026

2026

Show all 14 references

[9]

Hladký and D

J. Hladký and D. Piguet, Loebl–Komlós–Sós conjecture: the dense case,J. Combin. Theory Ser. B116(2016), 123–190, doi:10.1016/j.jctb.2015.07.004

2016 doi
[10]

Kővári, V

T. Kővári, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz,Colloq. Math.3(1954), 50–57

1954
[11]

Mi and Y

S. Mi and Y. Wang, Ramsey goodness of complete multipartite graphs with one large part, arXiv:2605.26826v2, 2026

2026 arXiv
[12]

Montgomery, M

R. Montgomery, M. Pavez-Signé, and J. Yan, Ramsey numbers of bounded degree trees versus general graphs, J. Combin. Theory Ser. B173(2025), 102–145, doi:10.1016/j.jctb.2025.02.004

2025 doi
[13]

Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc

M. Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319

1966
[14]

Szemerédi, Regular partitions of graphs, inProblèmes combinatoires et théorie des graphes (Colloq

E. Szemerédi, Regular partitions of graphs, inProblèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401

1976

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Aharoni, R

R. Aharoni, R. Holzman, D. Howard, and P. Sprüssel, Cooperative colorings and independent systems of representatives,Electron. J. Combin.22(2015), Paper P2.27, doi:10.37236/2488

work page doi:10.37236/2488 2015

[2] [2]

X. Bai, B. Li, W. Liu, and X. Zhang, Cooperative colorings of hypergraphs, arXiv:2408.03727, 2024

arXiv 2024

[3] [3]

Balla, A

I. Balla, A. Pokrovskiy, and B. Sudakov, Ramsey goodness of bounded degree trees,Combin. Probab. Comput. 27(2018), 289–309, doi:10.1017/S0963548317000554

work page doi:10.1017/s0963548317000554 2018

[4] [4]

S. A. Burr, Ramsey numbers involving graphs with long suspended paths,J. London Math. Soc.(2)24(1981), 405–413, doi:10.1112/jlms/s2-24.3.405

work page doi:10.1112/jlms/s2-24.3.405 1981

[5] [5]

Chvátal, Tree-complete graph Ramsey numbers,J

V. Chvátal, Tree-complete graph Ramsey numbers,J. Graph Theory1(1977), 93, doi:10.1002/jgt.3190010118

work page doi:10.1002/jgt.3190010118 1977

[6] [6]

Erdős, R

P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Multipartite graph–sparse graph Ramsey numbers, Combinatorica5(1985), 311–318, doi:10.1007/BF02579245

work page doi:10.1007/bf02579245 1985

[7] [7]

Erdős, R

P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Multipartite graph–tree Ramsey numbers, in Graph Theory and Its Applications: East and West, Ann. New York Acad. Sci.576(1989), 146–154

1989

[8] [8]

T. F. Bloom, Erdős Problem 550,https://www.erdosproblems.com/550, accessed 22 June 2026

2026