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.

1 S. A. Burr and P. Erdös, Extremal Ramsey theory for graphs, Utilitas Math. 9 (1976), 247-258.