Skip to main content
added 977 characters in body
Source Link
Andreas Blass
  • 73k
  • 5
  • 87
  • 162

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

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

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

Source Link
Andreas Blass
  • 73k
  • 5
  • 87
  • 162

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