0
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ cam you elaborate a bit thanks $\endgroup$ – james black Apr 26 '19 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.