20
$\begingroup$

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not colored edge blue or red. The goal is to avoid monochromatic $K_k$. The first player who completes a monochromatic $K_k$ loses. If $n$ is large enough the Ramsey theorem ensures that there can be no draw. Therefore someone has a winning strategy. My question is that:

Is there any pair $(n,k)$ such that $n<R(k,k)$ but in the corresponding game one of the players has a winning strategy?

$\endgroup$
12
  • $\begingroup$ "...coloring its edges": You mean: "coloring its vertices"? $\endgroup$ Sep 30, 2013 at 0:16
  • 3
    $\begingroup$ Why use only two equivalent colors? A natural generalization: fix $c\geq 2$ and $k_1,\ldots,k_c$ each at least $3$; two players alternate coloring a previously uncolored edge one of $c$ colors, and lose by completing a monochromatic $K_{k_i}$ of color $i$. The case $c=k_1=k_2=k_3=3$, $n=17$ is mentioned in the Wikipedia page en.wikipedia.org/wiki/Sim_(pencil_game) . One could also ask the same question for the game where one wins by completing a a monochromatic $K_{k_i}$ of color $i$. $\endgroup$ Sep 30, 2013 at 0:55
  • 1
    $\begingroup$ @suvrit The Ramsey game is different: there you have players Red and Blue who take turns to choose edges of their own colour, and whose goal is to create a monochromatic clique. The Ramsey game (for equal clique sizes) can never be a second player win, by strategy stealing (which does not work here). $\endgroup$
    – Ben Barber
    Sep 30, 2013 at 9:17
  • 1
    $\begingroup$ If the first player in the 5/3 has a winning strategy, it is to build a C_4 plus pending edge. No matter how stupid he plays, he will always be able to place a 4th edge without creating a triangle, so he can not lose before the 5th edge. And if he has an "at least tie" strategy, it is to build either C_4+pending or C_5. $\endgroup$ Sep 30, 2013 at 20:27
  • 1
    $\begingroup$ Maybe you know it, but in the $k=3, n=6$ game, the second player loses if he starts with an edge independent to the first player's first move. This is because the first player can pick the third edge that makes a matching and then use a mirroring strategy. $\endgroup$
    – domotorp
    Oct 2, 2013 at 6:01

1 Answer 1

20
$\begingroup$

This game can be described as an impartial edge colouring game on $K_n$ where creating a monochrome $K_k$ is not allowed, and the last player to make a move wins (normal play). Hence, it is equivalent to a nimber. I use the terms $P$-position and $N$-position sporadically to mean "a game state where the previous (resp. next) player has a winning strategy". I didn't calculate Sprague-Grundy values, but that is certainly doable. The game on $K_5$ with $K_3$ disallowed is a first player win. The game tree is small enough that I can give a complete strategy. I've also tried my best to make it RG/BY-colourblind readable by using dotted lines for anything that wasn't red or blue, but do let me know if it still causes problems and I could do something different.

As Flo Pfender mentioned, the first player should strive to create a monochromatic $C_4$ plus one edge, which I will call $C_4^+$

enter image description here

The dotted purple edge can be coloured red or blue, but the rest must be coloured blue, and the loser will be the player who makes the last move. Hence, the first player (us) will win if we can construct $C_4^+$ at any time. This will be the main goal of the strategy.

Beginning with one red edge, there are four non-isomorphic moves the second player can make:

enter image description here

Cases 1 & 2

The first two cases will elicit a similar response from us, which is to complete the triangle.

enter image description here

The second player can make 6 distinct moves from here, 3 with each colour.

A red response

enter image description here

For the first picture, we should complete the red $C_4$, and will ensure victory by adding one red line (from at least three possible) next turn. The latter two pictures can be combined into one by adding a red line, then on the next turn, our hero can create a $C_4^+$ by colouring either of the dotted green lines red. Since no other red edges can be drawn, they can only be blocked by colouring them blue, and with two possibilities, we will always have one available.

enter image description here

A blue response

The three pictures with blue lines added are as follows:

enter image description here

In the first two, we should complete to the picture below on the left, while in the third, we should play to the picture below on the right. Both of these positions have one triangle and a monotone length $2$ path, which is the same colour as the single triangle edge. These are $P$-positions (which is us) as we will show, and they come up again later in the final case, so I will refer to them as $T$ (for triangle) drawings.

enter image description here

First $T$

For the first, if our opponent plays any blue edge, we can complete it to a blue $C_4^+$:

enter image description here

For the first two, create a red $C_4$. It has two possible positions for an additional edge, so it can always be completed to a $C_4^+$. In the third, create a blue $C_4$, again with two places for a future blue edge. For the last two, colour a blue edge from the vertex with three red edges:

enter image description here

On the left, the blue $C_4^+$ cannot be blocked, while on the right, if the blue one is blocked by a red edge, then we can create a red $C_4^+$.

Second $T$

enter image description here

For the first four, make a red $C_4$, which can be completed to $C_4^+$ next turn, since there are at least two possibilities for the final edge. For the last one, draw a blue edge as shown - then the blue $C_4^+$ cannot be blocked.

enter image description here

Case 3

In the third case of the early game, our opponent has played the same colour as us on a non-adjacent edge. We should make it a monochrome path.

enter image description here

If they do not play a blue line to block the $C_4$, then we can play there, and we will have at least two options available for the final red line necessary for $C_4^+$. If they do play there, we will follow up with a red line to the untouched vertex (on the left below, which I will later refer to as a $Q$ drawing) - our opponent will be forced to block the $C_4^+$ again with a blue edge, which leaves a dotted black edge that can't be coloured safely, and three other edges which can only be coloured blue (on the right).

enter image description here

Each of the three safe edges to be coloured blue will not complete a blue triangle, either because the triangle would contain the black edge, or it contains an edge which is already red, so those are $3$ free moves. Thus, the second player will lose by having to play last.

Case 4

Finally, if your opponent chooses the opposite colour on their first turn, and doesn't play adjacent to you, you should connect the edges.

enter image description here

From here they have $13$ moves that continue the game, but fortunately we have covered most of them already. Three of the moves create a triangle plus one edge, which we know is an $N$-position from the first two cases.

enter image description here

The four possible moves from the bottom vertex to the two closest vertices can be extended to a $T$ drawing, again from the first section.

enter image description here

These should be played as follows, and note that the first two are now equivalent:

enter image description here

Of the four possible edges to colour red in the first image, three can be completed to $C_4^+$, and the last is the second player's response to $Q$, so the first player will win all of these.

enter image description here

Of the four possible blue edges, two can be completed to $C_4$ with two options for another blue edge. The other two should be followed by the dotted blue move, which makes them the same, and leaves two edges that can be given any colour, and one which cannot be safely coloured.

enter image description here

The three allowable blue edges can each be completed to $C_4^+$, while any of the four allowable red edges create a $T$ drawing plus one edge. Since we know that the $T$ drawing (triangle and monochrome 2-path) is a $P$-position, adding one edge makes it an $N$-position, so the first player wins.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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