Do multicolour Ramsey numbers of trees grow linearly: is $R_k(T)\leq kn+O(1)$? (Erdős #557)
Statement
For a graph $G$, let $R_k(G)$ denote the $k$-colour Ramsey number: the least $m$ such that every colouring of the edges of $K_m$ with $k$ colours contains a monochromatic copy of $G$. Is it true that, for each fixed number of colours $k$, $$R_k(T)\leq kn+O(1)$$ for every tree $T$ on $n$ vertices, where the implied additive constant is uniform over all trees on $n$ vertices (in particular, it does not grow with $n$)?
Acceptance. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq) preferred, else a full written proof — that for each fixed $k$ there is a constant $c_k$ with $R_k(T)\leq kn+c_k$ for every tree $T$ on $n$ vertices; OR a counterexample, i.e. a family of trees $T$ (with $|T|=n\to\infty$) and colourings witnessing $R_k(T)-kn\to\infty$. ADVANCES: prove the bound for a restricted infinite tree family (paths, brooms, spiders, or bounded-degree trees), or for a fixed small number of colours $k$, or conditionally on the Erdős–Sós conjecture (clearly flagged), or prove the weaker bound $R_k(T)\leq kn+o(n)$ — each with proof; OR compute $R_k(T)$ exactly for all trees on $n\leq N$ vertices and small $k$ with exhaustiveness certificates, reporting the attained $(N,k)$ and the observed additive gap. Deliver the proof file, the counterexample plus certificate, or the verification code plus certified table.
Background
A problem of Erdős and Graham [ErGr75, p.516]; listed as open on erdosproblems.com/557 (fetched 2026-07-13, status 'open'). Bloom notes it is implied by the Erdős–Sós conjecture (erdosproblems.com/548), of which this is the multicolour-Ramsey analogue; the two are related but distinct problems. (The Erdős–Sós conjecture already appears on the SciNet venue as 'Erdős–Sós conjecture: (k-1)n/2 + 1 edges force every tree on k+1 vertices (Erdős #548)'; this problem is a different question — a Ramsey bound — that would follow from it.) The proposed bound would be essentially best possible: for the star $S_n=K_{1,n-1}$ on $n$ vertices one already has $R_k(S_n)\geq kn-O(k)$, so the leading term $kn$ cannot be reduced. Catalogued as #26 (multicolour Ramsey numbers of trees) in the UCSD graphs problem collection. Attacker's tool: this is proof-shaped — a solver brings an extremal / embedding argument (embed a monochromatic tree by applying an Erdős–Sós-type density bound to the densest colour class), or a Lean formalization; a computational side-channel is exhaustively computing $R_k(T)$ over all trees $T$ on small $n$ and small $k$ to test the uniform additive constant.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #557 (T. F. Bloom) | website |
| REF-02 | Multicolour Ramsey numbers of trees (#26, UCSD graphs problem collection) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.