Ramsey Graph Game

(Symmetric) Ramsey Graph Game

Start with a complete graph – that is, a set of points all of which are connected by lines. Take turns coloring one of the edges. The winner is the first person to color edges which form a triangle.

For example, start with a complete graph on 5 points:

If the first player colored edges blue and the second player colored edges red, then the first player has a triangle and wins.

You can play on graphs with any number of vertices – to start with you probably want to stick with 4-8 vertices.

Questions:

1) If you started with 3 vertices, there is no way that someone will win (at most a player colors two edges) so the game ends in a draw. Is there always the possibility that the game ends in a draw? Or can you start with some number of vertices and always have a winner?

HINT: Consider 6 vertices.

ANSWER:

First, notice that a game on five vertices can end without either player having a triangle:

(This does assume that the players are playing randomly and without strategy.)

Now, consider a game played on six vertices, labeled A, B, C, D, E, and F. If the game ends without a winner, all the edges are colored. Then either the first player or the second has colored 3 of the edges from A to the other vertices. Suppose it is the first player, and that he or she colored the edges to B, C and D. In order for the first player not to have colored a triangle, he/she can have colored any of the edges between B, C and D. But then the second player would have a triangle of edges between B, C, and D! The same would happen if the second player had three edges from A or if they were to vertices besides B, C, and D. So any game on six vertices must have a winner.

Since any complete graph with more than six vertices contains a complete graph on six vertices, any game that starts with six or more vertices will have to have a winner.

Looking for the smallest complete graph such that, no matter how the edges are colored, one of the colors has a specific subgraph (such as the triangle above) is called Ramsey theory. In the case of the triangle, since we are trying to draw a complete graph on 3 vertices, we call this number R(3,3). That is, R(3,3) is the smallest number of vertices such that if you color all the edges between the vertices red and blue, there has to be a red complete graph on 3 vertices (a triangle) or a blue complete graph on 3 vertices. So we proved above that R(3,3) = 6. It has been proved that no matter which graph you pick for each player to try to color to win (or even if there are different graphs!) there is some number of vertices which will guarantee there is a winner. However, what this number is not known in most cases! To find out more about Ramsey theory, consider the following links:

(download a survey about Ramsey numbers)

2) Is there a strategy for winning? What is it? Does it help to be a first or second player?

HINT: If you were the first player and knew that the second player had a winning strategy, how could that help you?

ANSWER:

If the graph you are playing on is big enough to guarantee there is a winner, the first player has a winning strategy. Suppose the second player had a winning strategy – that is, he or she has a way to guarantee they get a triangle before the other player. Then the first player can make a random move to start, and then follow the second player’s winning strategy! This first random move can only help the first player to get a triangle, so the first player would have the winning strategy. Since the first player is then using the second player’s strategy, this argument is called strategy stealing. The same argument can be used to show that any time there is a winning strategy, the first player has it. But this tells us nothing about what the winning strategy is!

Suppose you are playing on a graph with six vertices – big enough to guarantee there is a winner. The key is for the first player (in blue) makes his or her first three moves from the same vertex, so that the second player has three triangles to block, but only two moves to do so. There are two cases, based on the first edge the second player draws: the second player’s first edge does not connect to the first player’s edges or it does. The second player’s first move is shown in solid red.

Case 1:

In the first case, the first player draws a second edge from either endpoint of the first edge to a vertex not yet used. (New edges are shown dotted.) The second player must then block the possible blue triangle with the second red edge. Then the first player can draw a third edge from the same vertex to the sixth vertex, which guarantees that there are two choices to complete a triangle on the next turn (shown in green below )– and the second player can’t block both of them! Therefore, the first player can win.

In the second case, the first player must draw the second blue edge from the vertex that has both a red and blue vertex. Then the second player must block the possible blue triangle, the first player can again draw a third blue edge from the same vertex to an unused vertex, and the second player cannot block both possible blue triangles (completed by green edges). Therefore the first player can win in this case as well.

Case 2:

Therefore this gives one winning strategy which allows the first player to win in 4 moves. Would it work for four vertices? Five vertices?

3) Extension: What if you want to play with more players?

ANSWER:

If you are playing with more players, to find when the game has to have a winner, we need to consider how many vertices the graph has to have to guarantee that one of the colors (now three or more) has a triangle. Ramsey theory has proved that no matter how many players you have, if you start with enough vertices there will be a winner! However, the number of vertices needed to guarantee a winner goes up a lot – for three players it takes 17 vertices. No one knows the smallest number of vertices it takes for four players in order to guarantee a winner!

If there are two or more other players, the strategy in the question above for winning doesn’t work – the other two players can block both the possible triangles. In order to have a winning strategy, you need to set it up to have more possible triangles than there are other players so there is still one left for you when it gets back to your turn!

However, the strategy stealing argument still works – the first player should have the winning strategy!

4) Extension: What if you are trying to get a different graph? Say a complete graph on four vertices in your color, or a cycle of four edges?

HINT: Can you build on the triangles you got above?

ANSWER: Ramsey theory has also proved that no matter which graph you pick for each player to try to color to win (or even if there are different graphs for different players!) there is some number of vertices which will guarantee there is a winner. However, what this number is is not known in most cases! We will write R(k,l) for the smallest number of vertices such that if we colored all the edges red and blue, there is either a red complete graph on k vertices or a blue complete graph on l vertices. We will write Kn for the complete graph on n vertices. (So K3 is a triangle.)

Above we proved that R(3,3)=6. Also note that R(k,1) = R(l,k) because if we can find either a red Kk or a blue Kl no matter how we color the edges, we could just switch all the colors on the edges and have either a red Kl or a blue Kk.

If you needed to win by coloring the edges of a K4, then to guarantee a winner we need at least R(4,4) vertices. Let’s try to find an estimate for R(4,4). If we can find a number of vertices n that guarantees either a red K4 or a blue K4 then we’ll know R(4,4) n. We can build up to a K4 by finding a triangle in one color and another vertex such that all the edges to the triangle are the same color.

So start at a vertex,v the way we did to find R(3,3). Call the set of vertices which have red edges from v S. Suppose S is big enough that we can guarantee that there is a triangle in red, as in Figure 1, or that there is a blue K4, as in Figure 2. Then we have either a red K4 or a blue K4! So we want to have at least R(3,4) red edges (so S has R(3,4) vertices), guaranteeing either a red K3 or a blue K4.

Figure 1 (K4 shown in thick lines)Figure 2 (K4 shown in thick lines)

But what if we don't have enough red edges for this to happen? Then we want there to be enough blue edges so that there is either a red K4 or a blue K3. This is just the same as the last question, except with colors switched! So if we don't have R(3,4) red edges, we need R(4,3)=R(3,4) blue edges! If there are 2R(3,4) - 1 edges from v, then there must be either R(3,4) red edges or R(3,4) blue edges by the pigeon hole principle. So if we have 2R(3,4) vertices, then we know we have a winner in the game when each player is trying to make a K4. (We showed R(4,4) 2R(3,4) )

But what is R(3,4)? It turns out that R(3,4)=9. We can get this by an argument similar to that above:

Start with a vertex v and let S be the set of vertices which have a blue edge from v. If S is big enough to have either a red K3 or a blue K3, then all together we get a red K3 or a blue K4 - just what we want! But we know that R(3,3) = 6, so if there are 6 blue edges from v, we get what we want. But what if there aren't 6 blue edges? If T is the set of vertices which have a red edge from v, then we need T to have either a red edge (a K2) or a blue K4. Well, if we have 4 vertices, then we know there is either a red edge or all the edges are blue - a blue K4. This says that R(2,4) = 4, and therefore if there are 4 red edges from v, we are fine. In order to guarantee 6 blue edges or 4 red edges, we need a total of 9 edges. (You can't make 9 edges with at most 5 blue edges and 3 red edges!) So we now know that R(3,4) 10.

But in fact, R(3,4) = 9! The key to noting that we can use the same argument on 9 vertices is by looking at the number of edges of each color to the vertices. By the argument above, in order to avoid a red K3 or a blue K4, we need to have 5 blue and 3 red edges at each of the 9 vertices. But each edge gets counted from 2 ends, so the number of times we count a blue edge should be even. But if each vertex has 5 blue edges, then we count blue edges a total of 45 times - this is a contradiction. Therefore, there is some vertex in a K9 which has either 6 blue edges or 4 red edges and we are done! This shows R(3,4) 9.

Note that this isn't enough to show that R(3,4) = 9. To show that, we need to show that there is some way to color K8 such that there is no red K3 or blue K4. (Then R(3,4) > 8, so with R(3,4) 9, we get R(3,4) = 9 since it must be an integer.) The following graph shows all the red edges of a coloring of K8, and there is no triangle. There is also no blue K4 in all the edges that are not shown. This shows that R(3,4) > 8.

Now, let's put the pieces together! R(3,4)=9 and we know that R(4,4) 2R(3,4) = 18. In fact, it can be proved that R(4,4) = 18. (Can you find a coloring of K17 such that there is no red K4 and no blue K4?) So if we have at least 18 vertices, then there must be a winner.

Amazingly, no one knows R(5,5)! We just know that 43 R(5,5) 49. Paul Erdös told this story: "Aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find [R(5,5)]. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value If the aliens demanded [R(6,6)], however, we would have no choice but to launch a preemptive attack" (Graham, R.L. and Spencer, J.H. Ramsey Theory, Scientific American July 1990: 112-117).

If you are playing that you need a cycle of 4 edges to win, 6 vertices still works to guarantee a winner. Can you figure out why?

5) Extension: What if both players are trying to avoid drawing a certain graph? This version of the game – when both players are trying to avoid drawing a triangle – is called Hexi or Sim. You can play it online at

HINT: Can both players win?

PARTIAL ANSWER: If the graph is guaranteed to have a triangle in one color by Ramsey theory, then there must be a loser! However, how to achieve this is a different question! Again, the first player has the winning strategy by strategy stealing.

This type of game is called an avoidance game.

Pekec’s Ramsey Graph Game:

The game is played in the same manner, except winning is defined differently. The first player wins in the same way – making a triangle. The second player wins by keeping the first player from making a triangle; the second player wins if all edges are colored and there is no triangle in the first player’s colors.

Therefore, for a game on 5 vertices, the second player would win the game below, even though there are no triangles in one color:

Questions: Can you come up with winning strategies for either player?

HINT: Can you use some of the ideas of Ramsey theory to find a strategy for the first player?

ANSWER: First, notice that since the two players have different goals, the first player can no longer steal a strategy from the second player!

We know from above that any graph on six vertices colored in red and blue must have a triangle in red or blue. Suppose we start with 12 vertices and the first player thinks of them split into two groups of six: A1, A2, A3, A4, A5, and A6 and B1, B2, B3, B4, B5 and B6. Then whenever the second player colors an edge within one group of six, the first player can color a matching edge. That is, if the second player colors the edge between A1 and A3, the first player will color the edge between B1 and B3. If the second player colors the edge between B2 and B6, the first player will color the edge between A2 and A6. If the second player doesn’t color an edge between one of these groups, then the first player can color an edge amongst the first group.

Why does the first player have to win with this strategy? As soon as all the edges amongst the A group or the B group are colored, there must be a triangle of one color. If it is blue for the first player, we are done! If it is red for the second player, then there must be a matching blue triangle in the other group, so the first player won then, too!

This same strategy works for any graph that you are trying to color – not just triangles – but you have to double the number of vertices required so that one of the two colors must have that graph in its color.

Pekec wrote of a strategy that does not require quite as many vertices and uses fewer moves. You can download information about it at .