On the multicolor Ramsey numbers of balanced double stars

The balanced double star on 2n+2 vertices, denoted S_n,n, is the tree obtained by joining the centers of two disjoint stars each having n leaves. Let R_r(G) be the smallest integer N such that in every r-coloring of the edges of K_N there is a monochromatic copy of G, and let R_r^bip(G) be the smallest integer N such that in every r-coloring of the edges of K_N,N there is a monochromatic copy of G. It is known that R₂(S_n,n)=3n+2 [8] and R₂^bip(S_n,n)=2n+1 [14], but very little is known about R_r(S_n,n) and R_r^bip(S_n,n) when r≥3 (other than the bounds which follow from considerations on the number of edges in the majority color class). In this paper we prove the following for all n≥1 (where the lower bounds are adapted from existing examples): • (r−1)2n+1≤R_r(S_n,n)≤(r−[Formula presented])(2n+2)−1, and • (2r−4)n+1≤R_r^bip(S_n,n)≤(2r−3+[Formula presented]))n. These bounds are similar to the best known bounds on R_r(P_2n+2) and R_r^bip(P_2n+2), where P_2n+2 is the path on 2n+2 vertices (which is also a balanced tree). We also give an example which improves the lower bound on R_r^bip(S_n,n) when r=3 and r=5.