In other news, I moved to Louisville yesterday to start my work as a graduate student and a graduate teaching assistant there. I was assigned a class to TA for, but it conflicts with my own class schedule. So, that will have to get fixed. It seems the mathematics secretary is a position in transition. The old secretary is becoming the business manager, and the new secretary is flustered and overwhelmed. So, it may be a bit until everything gets sorted out. It seems that most TAs run recitation sessions, give and grade quizzes, and hold office hours. None of that seems to strenuous and the professors seems laid back and likable. More on that story as it develops.
Now I might try a little math: This is the introduction to the problem I worked on during my REU (Research Experience for Undergraduates) in McMinnville, OR.
Alice and Bob are friends who are going to play a game. The game board is a piece of paper with a graph drawn on it. The graph consists of some open dots, called vertices. The vertices are connected by lines called edges. The game is played by coloring the vertices with crayons. Alice and Bob only have a limited number of crayons, though. Let's say they have r crayons, each a different color. A color (i.e. red) is legal for a vertex as long as none of that vertex's neighbors are red. So, if two vertices are connected by an edge, those two vertices cannot be colored the same color. Alice always goes first. She wins if eventually all the vertices are colored. Bob tries to thwart Alice. He wins if at any point, a vertex cannot be colored. This means that each of the r colors appear among that vertex's neighbors.
Now, each and every graph has a number associated with it in relation to this game. It is called the game chromatic number. "Game" because the regular chromatic number of a graph is the least number of colors needed for Alice to color the graph, without Bob taking his turns. "Chromatic" refers to colors. So, the game chromatic number of a graph is the least number of colors Alice needs to have a winning strategy against Bob. In other words, its not enough for Alice to win a game with, say, six colors. She needs to be able to win every game on that graph with six colors to make six that graph's game chromatic number (she cannot rely on Bob being stupid).
So, let's look at an example. Let's consider a binary tree. A binary tree is a graph where one vertex is designated as the root, and it has at most two neighbors (which are not neighbors of each other), called its children. Each other vertex has at least one neighbor and at most three neighbors (all of which are not neighbors of each other), its parent, and up to two children. I'm going to try to include a picture of an example of a binary tree. If it doesn't work, sketch out the description above.
Well, that seems to have worked! I'm still getting the hang of it. Ok, the red arrow indicates the root (yes, it's at the top). The green arrows are the root's children and are known as the 1st generation. The blue arrow indicates the parent of the vertex pointed to by the purple arrow. Notice that the blue arrowed vertex has only one child, and the purple arrowed vertex has no children. This is perfectly legal. However, the root is the only vertex without a parent.
Now let's color the graph (not by playing the game--this is just Alice coloring right now). How can we do it so no two neighbors have the same color? Let's color the root red. Then it's children must not be red, but they can both be blue, since they are not neighbors themselves. Next, all the children of the blue vertices can be red since they are not neighbors of each other, and they are not neighbors of the root. You should see the pattern: alternating colors as you move down the generations will give a proper coloring of this tree (any tree, in fact). A proper coloring is simply one where no two neighbors have the same color. Let's see if I can add a picture of that.
Now, finally, let's revisit the game. We can easily show that Alice will always win if she and Bob have four crayons. We'll also show that she can win with three colors. But, we'll show that two colors is not enough for her to win.
The first part is easy: no vertex has more than 3 neighbors. Therefore, there are at most three distinct colors among the neighbors of any one vertex. This means that Alice (or Bob) always has the fourth color available to use if necessary. Ok, so four is enough, but what about three?
Let's number the vertices for easy reference:
If Bob colors 1 or anything on the right side, color 3. (If Bob colored 12 or 13, use the same color he used)
If Bob colors 3, color 6.
If Bob colors anything on the left side, color 4 or 5, whichever is closest.
The important vertices are 2, 3, 4, 5, and 6, since these are the only vertices with enough neighbors that would allow Bob to force a win. If, at any time, Alice finds she cannot follow her strategy because the vertex it tells her to color is already colored, she should color one of the important vertices. Once those have been colored, Alice cannot lose.
Now, why can't Alice win with just two colors? Suppose Alice colors a vertex (any of them). Bob moves two vertices away and uses the second color. Now, the vertex in between cannot be colored and Bob automatically wins.
We have shown that 3 colors are enough for Alice to win the game on this graph, and two colors are not enough. So, the game chromatic number of this graph is 3.
It is now very late, and I'm headed to bed. There is a high probability that there is some mistake in the above, although I hope not. It is interesting that if I had given the last vertex in the 2nd generation a second child, then I don't think Alice could win with three colors. I haven't checked this, but I'm pretty sure she would need 4.
This was just an example graph/game. Results in this area are proved about entire classes of graphs, not just individual graphs. For instance, it is known that the game chromatic number of any tree (a graph with no cycles) must be less than or equal to 4. In a future post, I'll describe some variants on the game and some results thereof.
Charlie
No comments:
Post a Comment