# Ramsey numbers Special Case

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)

## 2 Answers

$$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.

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.

• cam you elaborate a bit thanks – james black Apr 26 '19 at 15:03