Ramsey numbers Special Case

Question

Show that there exists R(s)=N such that all $K_N$ complete graphs (with blue and red two colors) must contain a monochromatic s-vertex star. Find a formula for R(s).

I know the formula for cliques on ramsey numbers and its existence; do i follow similar approach on showing R(s) also exists (by induction)? or is there an easier way?

I believe that R(s)=(s-1)*2 for even s as each vertex connects to (s-1)*2-1 edges and it is then obvious that an s-star from one vertex needs to connect to s-1 edges so we have at least either blue s-star or red s-star. However, is this the minimum number? (i believe i should seperate even and odd s so there should be two cases)

Answer 1

You have established $2s-2$ points must have a star. Here I show $2s-4$ points don't have to have a star. That still leaves $2s-3$ points...

With $2s-4$ points, divide them into two groups $A$ and $B$, of $s-2$ points each. Edges between two $A$ points are red; edges between two $B$ points are red; and edges between an $A$ point and a $B$ point are blue. Each point is attached by $s-3$ red edges and $s-2$ blue edges, so we don't get an $s$-star.

Answer 2

$2s-3$ points suffice if $s$ is odd. Proof: Suppose we had a counterexample coloring of the complete graph on $2s-3$ points. Each point $p$ has $2s-4$ incident edges, and exactly half of them, $s-2$, must be red, because if you had more (or fewer) than that many red edges, then the endpoints of those edges (or the endpoints of the other edges) and $p$ would constitute an $s$-vertex star colored all red (or all blue). But then the subgraph consisting of the red edges would have an odd number (namely $2s-3$) of vertices of odd degree (namely $s-2$), which is well-known to be impossible in any finite graph.

On the other hand, when $s$ is even, $2s-3$ points do not suffice. To produce a counterexample, think of the $2s-3$ points as the elements of the cyclic additive group $\mathbb Z/(2s-3$. Partition the set of all $2s-4$ non-zero elements into the $s-2$ two-element sets of the form $\{x,-x\}$. (Note that these really are two-element sets, since $x\neq0$ and $2s-3$ is odd, so $x\neq-x$ in $\mathbb Z/(2s-3)$.) Since $s-2$ is even, we can select a family consisting of exactly half of these $s-2$ pairs. Now color an edge $\{a,b\}$ red iff $a-b$ is in one of the selected pairs. (Note that this makes sense because $a-b$ and $b-a$ are in the same pair; we don't need to think in terms of directed edges.) The selected pairs contain, altogether, $s-2$ numbers. So each vertex gets exactly $s-2$ of its incident edges colored red and (therefore) exactly $s-2$ colored blue. No vertex gets $s-1$ incident edges of the same color, so there's no monochromatic $s$-vertex star.