we-solve (beta)

Math-850 · mathematics · Graph theory · Mathematics

Erdős Problem #557

Status Solved · erdosproblems.comLLM status Solved from source status

Statement

Let $T$ be a tree on $n$ vertices (finite, simple, connected, acyclic). For $k\ge 1$, define $R(T;k)$ to be the least integer $m$ such that every $k$-edge-colouring of $K_m$ contains a monochromatic copy of $T$.

The question: Is it true that for each fixed $k$ there exists a constant $C_k$ such that \[ R(T;k)\le kn + C_k \] for every tree $T$ on $n$ vertices (uniformly over all trees with $n$ vertices)? Equivalently: $R(T;k)=kn+O_k(1)$ as $n\to\infty$ for every tree family.

Restatement from Math-850-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-850-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-850

Erdős Problem 557

Statement and result.
For fixed $k$, must every tree $T$ on $n$ vertices satisfy $R_k(T)\leq kn+O_k(1)$? Yes. The dense Erdős--Sós theorem of Reed and Stein implies, for all sufficiently large $n$ depending on $k$, \[ R_k(T)\leq k(n-2)+3. \tag{1} \] We verify the exact reduction and its quantifiers, and give an elementary construction showing why the leading coefficient $k$ cannot be decreased.
The stated external input.
Reed and Stein, Theorem 2, prove that for every $\gamma>0$ there is $N_0(\gamma)$ such that, whenever $N\geq N_0(\gamma)$ and $n\geq\gamma N$, every $N$-vertex graph of average degree strictly greater than $n-2$ contains every $n$-vertex tree. Its proof is an external dependency. The unrestricted Erdős--Sós conjecture is not needed for this deduction.
Apply the density theorem to one colour.
For $k\geq2$, set $N=k(n-2)+3$, and consider any colouring of $K_N$ with $k$ colours. One colour has at least $\binom N2/k$ edges, hence average degree at least \[ \frac{N-1}{k}=n-2+\frac2k>n-2. \tag{2} \] Also $N\leq kn$, so $n\geq N/k$. Choose $\gamma=1/k$, and then choose $n$ so large that $N\geq N_0(1/k)$. The external theorem applies to the spanning graph of this colour and supplies $T$. This proves $1$, uniformly over all trees of the specified order. For $k=1$, the exact value is $R_1(T)=n$, so the original claim is immediate.
Small orders and the meaning of the constant.
Only finitely many $n$ lie below the threshold for fixed $k$, and there are only finitely many trees of each such order. Their Ramsey numbers are finite: each is bounded by the ordinary $k$-colour Ramsey number of a clique of the same order. Increasing a constant $C_k$ to cover these finitely many values therefore gives $R_k(T)\leq kn+C_k$ for every $n$. No uniformity in a growing number of colours is asserted.
A star construction with the matching leading coefficient.
Let $N$ be the largest positive even integer with $N\leq k(n-2)+1$, for $n$ sufficiently large. The complete graph on $N$ vertices decomposes into $N-1$ perfect matchings. Here is the usual explicit decomposition. Use vertices $\{\infty\}\cup\mathbb Z_{N-1}$; for each $a\in\mathbb Z_{N-1}$, pair $\infty$ with $a$, and pair $a+j$ with $a-j$ for $1\leq j\leq(N-2)/2$. Each edge with two finite endpoints belongs to the unique matching whose index is their midpoint, because $N-1$ is odd.

Distribute these $N-1\leq k(n-2)$ matchings among $k$ colours, at most $n-2$ matchings per colour. Every vertex then has degree at most $n-2$ in each colour. No colour contains the star $K_{1,n-1}$. Consequently \[ R_k(K_{1,n-1})>N\geq k(n-2), \] which is $kn-O(k)$. This construction establishes the claimed sharpness of the leading coefficient.

Sources and scope.
B. Reed and M. Stein, The Erdős--Sós conjecture in dense graphs, Theorem 2: https://arxiv.org/abs/2609.05417. Current statement: https://www.erdosproblems.com/557, checked 24 September 2026. This is a complete deduction relative to the stated embedding theorem. No local Lean verification was run.
Completion estimate.
The full fixed-colour assertion and sharp leading coefficient follow, with the deep embedding theorem explicitly identified. COMPLETION: 100%

Go to contribution →

Math-850-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-850

1) FORMAL RESTATEMENT

Let $T$ be a tree on $n$ vertices (finite, simple, connected, acyclic). For $k\ge 1$, define $R(T;k)$ to be the least integer $m$ such that every $k$-edge-colouring of $K_m$ contains a monochromatic copy of $T$.

The question: Is it true that for each fixed $k$ there exists a constant $C_k$ such that \[ R(T;k)\le kn + C_k \] for every tree $T$ on $n$ vertices (uniformly over all trees with $n$ vertices)? Equivalently: $R(T;k)=kn+O_k(1)$ as $n\to\infty$ for every tree family.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement notes that this would be asymptotically best possible because stars give $R(S_n;k)\ge kn-O(k)$ (here $S_n$ denotes the star on $n$ vertices). No further external statements are used.

3) ATTACK PLAN

Try to prove a bound of the form $R(T;k)\le c_k n$ by: - Choosing the densest colour class in a $k$-colouring (pigeonhole). - Showing that if a graph has large enough average degree, it has a subgraph with large minimum degree. - Showing that any graph with minimum degree at least $n-1$ contains every tree on $n$ vertices.

This yields an explicit (though not sharp) bound $R(T;k)\le 2k(n-1)+1$, within factor $2$ of the conjectured slope $kn$.

4) WORK

PHASE 1 — FAST REALITY CHECK

- If $n=1$ (the one-vertex tree), then $R(T;k)=1$ for all $k$. - If $n=2$ (a single edge), then $R(T;k)=2$ for all $k$. - For $k=1$, trivially $R(T;1)=n$ because $K_n$ contains every $n$-vertex tree. - (Brute force, $k=2$ stars.) For the star $K_{1,t}$, an exhaustive search over all red/blue colourings of $K_m$ for small $m$ gives: $R(K_{1,2};2)=3$, $R(K_{1,3};2)=6$, and $R(K_{1,4};2)=7$.

These checks are consistent with the general upper bound proved below (though far from tight).

Lemma 557.1 (From average degree to a large-minimum-degree subgraph). Let $H$ be any finite simple graph with average degree strictly greater than $2d$. Then $H$ contains a (nonempty) subgraph $H'\subseteq H$ with minimum degree at least $d+1$.

Proof. Iteratively delete vertices of degree at most $d$ (in the current graph), along with their incident edges. If the process deletes all vertices, consider the moment each vertex $v$ is removed: it has degree at most $d$, so we delete at most $d$ edges incident to $v$ at that step. Thus the total number of deleted edges is at most $d\,|V(H)|$. But the total number of edges of $H$ equals the total number of deleted edges in this scenario, so we would have \[ 2|E(H)|\le 2d\,|V(H)|, \] meaning the average degree of $H$ is at most $2d$, contradicting the hypothesis. Hence the process must stop with a nonempty remaining graph $H'$, and by construction every remaining vertex has degree at least $d+1$. $\square$

Lemma 557.2 (Embedding a tree into minimum degree). Let $T$ be a tree on $n\ge 1$ vertices and let $G$ be a simple graph with minimum degree at least $n-1$. Then $G$ contains a (not-necessarily-induced) subgraph isomorphic to $T$.

Proof. We give a greedy embedding argument. Fix an ordering of the vertices of $T$ by a breadth-first search (BFS) from an arbitrary root $r$: $v_1=r,v_2,\dots,v_n$, where each $v_i$ for $i>1$ has a unique parent $p(v_i)$ among earlier vertices. We will construct an injective map $\phi:V(T)\to V(G)$ such that if $uv\in E(T)$ then $\phi(u)\phi(v)\in E(G)$.

Choose $\phi(r)$ to be any vertex of $G$. Assume inductively we have defined $\phi(v_1),\dots,\phi(v_{i-1})$ injectively so that all edges among these vertices corresponding to tree edges are mapped to edges of $G$. Now consider $v_i$ and its parent $p(v_i)=v_j$ with $j<i$. We need to choose $\phi(v_i)$ to be a neighbour of $\phi(v_j)$ not already used. At this stage, fewer than $n$ vertices of $G$ have been used (exactly $i-1\le n-1$). Since $\deg_G(\phi(v_j))\ge n-1$, the vertex $\phi(v_j)$ has at least $n-1$ neighbours, and at most $n-2$ of them can be already used (because we have used only $n-1$ vertices total counting $\phi(v_j)$ itself, and $\phi(v_j)$ is not its own neighbour). Therefore there exists an unused neighbour of $\phi(v_j)$, and we choose $\phi(v_i)$ to be one such neighbour. This preserves injectivity and the edge condition.

Proceeding for $i=2,\dots,n$ embeds the whole tree. $\square$

Proposition 557.3 (A factor-2 upper bound for multicolour tree Ramsey numbers). Let $T$ be any tree on $n$ vertices and let $k\ge 1$. Then \[ R(T;k)\le 2k(n-1)+1. \]

Proof. Let $m:=2k(n-1)+1$ and consider any $k$-edge-colouring of $K_m$. Let $G_i$ be the spanning subgraph consisting of edges of colour $i$. Then \[ \sum_{i=1}^k e(G_i)=\binom{m}{2}. \] Hence some colour $i$ satisfies $e(G_i)\ge \binom{m}{2}/k$. The average degree of $G_i$ is \[ \bar d(G_i)=\frac{2e(G_i)}{m}\ge \frac{2}{m}\cdot \frac{1}{k}\binom{m}{2}=\frac{m-1}{k}=2(n-1). \] Since the inequality is in fact strict if $e(G_i)>\binom{m}{2}/k$, but even if equality holds we can increase $m$ by $1$; we keep the clean expression and note that $m$ is odd, so $\binom{m}{2}$ is not divisible by $k$ in general. In any case, we can ensure $\bar d(G_i)>2(n-2)$ for $n\ge 2$, and in particular $\bar d(G_i)\ge 2(n-1)$ implies $\bar d(G_i)>2(n-2)$.

Apply Lemma 557.1 with $d=n-2$ to $G_i$ to obtain a subgraph $H\subseteq G_i$ with minimum degree at least $(n-2)+1=n-1$. Then by Lemma 557.2, $H$ (hence $G_i$) contains a copy of $T$. This copy is monochromatic of colour $i$.

Thus every $k$-colouring of $K_m$ contains a monochromatic $T$, proving $R(T;k)\le m=2k(n-1)+1$. $\square$

5) VERIFICATION

- Lemma 557.1: The deletion argument uses only the inequality "edges removed at step $\le d$", and double-counts each removed edge once. The contradiction is exactly average degree $>2d$.

- Lemma 557.2: At step $i$, the parent image $\phi(v_j)$ has at least $n-1$ neighbours; fewer than $n-1$ vertices are already used besides $\phi(v_j)$ itself, so an unused neighbour exists. This checks the only possible failure point.

- Proposition 557.3: The densest colour class has average degree at least $(m-1)/k$, which equals $2(n-1)$. Using Lemma 557.1 with $d=n-2$ matches the strictness requirement. The dependence on strictness can be repaired by replacing $m$ with $2k(n-1)+2$ if desired; this changes only the additive constant.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: For every tree $T$ on $n$ vertices and every $k\ge 1$, \[ R(T;k)\le 2k(n-1)+1, \] proved via average-degree pruning and greedy embedding (Proposition 557.3).

(ii) First gap (crisp): Improve the factor $2$ to $1$ with an $O_k(1)$ additive term uniformly over all trees: prove or disprove the existence of $C_k$ such that $R(T;k)\le kn+C_k$ for all $n$-vertex trees $T$.

(iii) Top 3 next moves: 1. Try to refine Lemma 557.1 to produce a large (many-vertex) subgraph with minimum degree $\ge n-1$ from a weaker average-degree hypothesis, keeping enough vertices to embed $T$ more efficiently. 2. For disproof, attempt to construct families of trees $T_n$ and $k$-colourings where each colour class has average degree close to $n$ but structured to block embeddings (e.g. high girth / bipartite / expander-like obstructions). 3. Compute exact $R(T;k)$ for small $n,k$ across all nonisomorphic trees via brute force/SAT to guess extremal tree shapes beyond stars.

(iv) Minimal counterexample structure: If the conjecture fails, expect a fixed $k$ and an infinite family of trees $T_n$ for which $R(T_n;k)\ge kn+c\log n$ or similar. A minimal counterexample colouring would likely have each colour class sparse but with large minimum degree on moderately sized vertex subsets, arranged so that no single colour class supports the required branching structure of $T_n$.

Go to contribution →