pith. sign in

arxiv: 2606.23659 · v1 · pith:SYC6YKEFnew · submitted 2026-06-22 · 🧮 math.CO

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

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

Pith reviewed 2026-06-26 07:41 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey numberstreescomplete multipartite graphsErdős problem 550graph embeddingsSzemerédi regularityhypergraph obstructions
5
0 comments X

The pith

For any fixed complete multipartite graph and sufficiently large tree T, the Ramsey number R(T, K_{m1,...,mk}) is at most (k-1) times the bipartite case plus m1.

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

The paper establishes an explicit upper bound relating the Ramsey number of a tree against a k-partite complete graph to the corresponding number against a 2-partite complete graph. For fixed k and part sizes m1 through mk, and for every tree T on n vertices with n large enough, the inequality R(T, K_{m1,...,mk}) ≤ (k-1)(R(T, K_{m1,m2})-1) + m1 holds. This directly resolves Erdős Problem 550 by showing that the general multipartite case reduces to the bipartite case via a simple linear expression. A reader would care because the result supplies a concrete way to bound or compute these numbers without treating each number of parts separately.

Core claim

For fixed integers k≥2 and 1≤m1≤⋯≤mk, every sufficiently large n, and every n-vertex tree T, the Ramsey number satisfies R(T,K_{m1,…,mk}) ≤ (k-1)(R(T,K_{m1,m2})-1)+m1.

What carries the argument

The new off-Turán tree-embedding theorem, which embeds large trees into dense graphs while avoiding multipartite obstructions, combined with a compactness-and-rounding theorem on bounded-rank hypergraph obstructions.

Load-bearing premise

The off-Turán tree-embedding theorem holds and correctly places trees inside graphs that avoid the target multipartite subgraphs.

What would settle it

An explicit counterexample: a fixed k, fixed part sizes m1≤⋯≤mk, and a sequence of larger and larger trees T_n for which R(T_n, K_{m1,...,mk}) exceeds (k-1)(R(T_n, K_{m1,m2})-1)+m1.

read the original 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 a new off-Tur\'an tree-embedding theorem with a compactness-and-rounding theorem for represented bounded-rank hypergraph obstructions. The embedding theorem follows from Szemer\'edi regularity and a local regular-matching embedding lemma of Hladk\'y and Piguet. The compactness argument uses shadow hypergraphs to retain obstructions whose vertices escape along the limiting sequence.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript resolves Erdős Problem 550 by proving that for fixed integers k≥2 and 1≤m1≤⋯≤mk, and for every sufficiently large n (depending only on k and the m_i) and every n-vertex tree T, the Ramsey number satisfies R(T,K_{m1,…,mk}) ≤ (k-1)(R(T,K_{m1,m2})-1)+m1. The argument proceeds by establishing a new off-Turán tree-embedding theorem (via Szemerédi regularity and the Hladký–Piguet local regular-matching lemma) and combining it with a compactness-and-rounding theorem for represented bounded-rank hypergraph obstructions that employs shadow hypergraphs to control escaping vertices.

Significance. If correct, the result completely settles the stated question of Erdős, Faudree, Rousseau, and Schelp by supplying an explicit linear reduction from the k-partite to the bipartite case that holds uniformly over all trees on n vertices. The new embedding theorem and the shadow-hypergraph compactness technique constitute reusable technical contributions to the study of tree Ramsey numbers and hypergraph Turán problems.

minor comments (2)
  1. [Abstract] The dependence of the threshold for 'sufficiently large n' on the fixed parameters k and m_i is stated but could be made more explicit in the statement of the main theorem (e.g., by adding a sentence after the displayed inequality).
  2. Notation for the complete multipartite graph K_{m1,…,mk} and the Ramsey number R(·,·) is introduced without a preliminary definition paragraph; a short notation subsection would aid readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. We are pleased that the resolution of Erdős Problem 550 and the technical contributions were viewed favorably.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external standard lemmas

full rationale

The claimed bound reduces the k-partite Ramsey number to the 2-partite case via a new off-Turán embedding theorem (proved from Szemerédi regularity + Hladký-Piguet local lemma) plus a compactness-rounding argument on hypergraph obstructions using shadow hypergraphs. Both supporting results are external or newly introduced without self-referential reduction; no equation equates the target bound to a fitted input, no self-citation is load-bearing, and no ansatz or uniqueness theorem is smuggled from prior author work. The result is for sufficiently large n depending only on fixed parameters and holds uniformly over trees, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim depends on two new theorems introduced in the paper (off-Turán embedding and compactness-rounding for hypergraphs) plus standard tools from extremal graph theory. No free parameters or invented entities.

axioms (2)
  • standard math Szemerédi regularity lemma
    Invoked to prove the off-Turán tree-embedding theorem as stated in the abstract.
  • standard math Local regular-matching embedding lemma of Hladký and Piguet
    Used in the embedding theorem per the abstract.

pith-pipeline@v0.9.1-grok · 5703 in / 1380 out tokens · 34287 ms · 2026-06-26T07:41:12.361229+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 7 canonical work pages

  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

  9. [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

    work page doi:10.1016/j.jctb.2015.07.004 2016

  10. [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. [11]

    Mi and Y

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

    Pith/arXiv arXiv 2026

  12. [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

    work page doi:10.1016/j.jctb.2025.02.004 2025

  13. [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. [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