Upper bound for Ramsey on trees
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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 2n2. \]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 \( (n2)m/2\) edges contains every tree \( T\) on \( n\) vertices. If this conjecture were true, it would imply the above conjecture.
Bibliography  

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