Ramsey Number for Star graphs

Question

For two graphs $H_1$ and H2, the Ramsey number $r(H_1, H_2)$ is the minimum number r so that in any red-blue coloring of the edges of the complete graph Kr on r vertices there is necessarily either a red copy of $H_1$ or a blue copy of $H_2$ (or both).

Let $\def\star#1{K_{1,#1}}\star n$ denote the star with $n$ edges. Compute the Ramsey number $r(\star n, \star m)$ for all values of $m$ and $n$.

My approach was to look at a vertex in $K_r$ and observe when its degree is big enough for there to be enough edges such that one of the stars has to appear. My problem is that I do not understand how to show it's the minimal number (or even if it is true).

My second issue is that I was given a hint that the formula depends on the parity of $n$ and $m$, and my approach does not address this, which suggests it may be flawed.

Would appreciate some guidnace.

Thanks.

Answer 1

For brevity, let's say $S_n = K_{1,n}$ and $R(m,n) = R(S_m, S_n)$. As we are not using the standard $R$ function (which uses complete subgraphs), there is no confusion.

First, some easy bounds:

1. $$R(m,n)≤R(m+1,n)\\R(m,n)≤R(m,n+1)$$

   Take a "good" coloring of $K_c$ where $c=R(m,n)-1$ (one which proves $R(m,n)>c$). This graph by hypothesis does not contain any red $S_m$ nor blue $S_n$, so it doesn't contain any red $S_{m+1}$ nor blue $S_{n+1}$ (as bigger stars always contain smaller stars).

2. $$m+n≤R(m,n) \text{ if any of the arguments is odd}$$

   Suppose $m=2y+1$ is odd (otherwise rename and mix). Take $K_{m+n-1}$, label its vertices with numbers from $0$ to $m+n-2$ and colour an edge $(ij)$ red whenever $$i-j\in\{-y,\dots,y\} \mod m+n-1.$$ It's very easy to see that each vertex will have then $2y=m-1$ red edges and $n-1$ blue edges. So $m+n-1<R(m,n)$.

3. $$R(m,n)≤m+n$$

   In any $K_{m+n}$ all vertices have $m+n-1$ edges, so either there are $m$ red edges or there are $n$ blue edges.

4. $$R(m,n)≤m+n-1 \text{ if all of the arguments are even}$$

   Proposition: The number of vertices of odd degree in any graph is even.

   This is because all edges are incident on two (not necessarily distinct) vertices, so the sum of the degrees of all vertices is exactly the sum of the "degrees" of the edges (which is 2), so it is even. On the other side, a sum of an odd number of odd numbers is odd.

   Suppose there is a coloring of $K_{m+n-1}$ with no red $S_m$ nor blue $S_n$. As every vertex of $K_{m+n-1}$ has degree $m+n-2$, every vertex has exactly $m-1$ red and $n-1$ blue incident edges.

   Now take the red subgraph. This graph has all vertices of degree $m-1$ (odd), and has exactly $m+n-1$ vertices (odd). So this graph does not exist, so we couldn't have the coloring in the first place.

Now, with these inequalities, it's easy to get to the solution:

$$ R(K_{1,n}, K_{1,m}) = \begin{cases} m+n-1 & \text{ when both $m$ and $n$ are even}\\ m+n & \text{ otherwise}. \end{cases} $$