An upper bound on the Ramsey number of trees (Q1821795): Difference between revisions

Let f(k,n) denote the smallest integer m so that, if the edges of the complete graph on m vertices are colored with k colors, then there exists a monochromatic subgraph with minimum degree at least n. Given a graph G, the Ramsey number r(G,k) is the smallest integer m so that every k- coloring of the edges of the complete graph on m vertices yields a monochromatic copy of G. The author proves: Theorem. \(f(k,n)\leq (n- 1)(k+\sqrt{k(k-1)})+2;\) which gives: Corollary. \(r(T_ n,k)\leq (n- 1)(k+\sqrt{k(k-1)})+2;\) where \(T_ n\) is any tree on n vertices.