# Upper bound for Ramsey on trees

For two graphs $$G$$ and $$H$$, let $$r(G,H)$$ denote the smallest integer $$m$$ satisfying the property that if the edges of the complete graph $$K_m$$ are colored in red and blue, then there is either a subgraph isomorphic to $$G$$ with all red edges or a subgraph isomorphic to $$H$$ with all blue edges. The classical Ramsey numbers are those for the complete graphs and are denoted by $$r(s,t)= r(K_s, K_t)$$. If $$s=t$$, we write $$r(s)=r(s, s)$$.

Many Ramsey numbers have been determined for special families of graphs, including various combinations of paths, trees, stars and cycles. However, the following problem[1] on Ramsey numbers for trees is still open.

# Conjecture (proposed by Burr and Erdös [1])

For any tree $$T$$ on $$n$$ vertices, $r(T) \leq 2n-2.$

Clearly, for a star on $$n$$ vertices, equality holds. So, the above conjecture can be restated as $$r(T) \leq r(S_n)$$, where $$S_n$$ denotes the star on $$n$$ vertices.

The above problem is closely related to a conjecture by Erdös and Sós. This conjecture asserts that every graph with $$m$$ vertices and more than $$(n-2)m/2$$ edges contains every tree $$T$$ on $$n$$ vertices. If this conjecture were true, it would imply the above conjecture.