Playing Games and Packing Graphs

Elwyn Berlekamp is a famous mathematician who has made seminal contributions to many aspects of both theory and practice. His work on decoders for Reed-Solomon codes, with James Massey, is both beautiful and practical. Without this work many consumer products would be impossible—for example, Reed-Solomon codes are used in disc storage and in wireless networks. Elwyn has also worked on subjects of potentially less practical application, such as combinatorial game theory. He co-authored with John Conway and Richard Guy the book Winning Ways for your Mathematical Plays. He also has the same birthday as I do: September —perhaps the least important fact.

Today I would like to talk about work related to combinatorial game theory. Right now the 2010 World Chess Championship is in progress between Viswanathan Anand and Veselin Topalov in Sofia, Bulgaria. I am a chess “wood pusher,” but am inspired by the match to think about mathematical games.

I vividly recall the first time I met Elwyn. I was visiting Berkeley in 1979 on a job interview for a faculty position in the department of Computer Science. My first appointment was with him, since he was then the chair of the department. I recall sitting down in his office, and before I could say a word he said:

“Dick, I want to know what is the probability that you will accept an offer, if we make you one.”

It was a job interview and I had planned answers for all the usual questions: what did I do, what were my reasons for leaving Yale, and so on. But this question surprised me. I thought for a second and said “I would accept with probability 1/3.” He said fine, and started to ask a more standard question, when I interrupted and said “was my answer okay?” Elwyn said it was fine—if it had been too high he would have worried why I was so anxious to leave Yale, and if it was too low he would not have wasted any more time on the interview. I never knew if I had said “1/10” would he really have terminated the interview. Oh well.

After a while we switched to a favorite topic of Elwyn: playing games and in particular playing dots and boxes. I almost agreed to play a game, when he told me he had not lost in over ten years. I thought playing a game with the chair—a game I was sure to lose—might not be the best way to impress him. Instead I asked him for a pointer on how to play the game. I knew this simple game: each player adds lines, if you make a box you go again, and the player with the most boxes wins. I never had thought the game was more than just a kids game. I was very wrong.

Elwyn knew many strategies, he explained a basic one to me. He said it would allow me to beat most people, and he was right.

Here is the trick. The red edge in figure (1) was just added. A beginner would fill in all the boxes to form the middle figure (2). This loses. A better player would only fill in some of them, see the right most figure (3), and would win. Very clever. Elwyn told me to master the game there were many more sophisticated tricks, but even this simple one is quite neat.

A Colorful Game

There are many combinatorial games. These games by definition are like chess: each player has full knowledge of the state of the game and there is no randomization. A game like backgammon is not allowed, since it uses dice; a game like checkers is allowed.

A wonderful combinatorial game is one first popularized by the famous Martin Gardner. But there has been quite a bit of recent work on this game and its connection to other problems. There are two players: Alice and Bob—perhaps I should use other names, but Alice and Bob seem to be everywhere these days. They fix a planar graph and a number of colors . Suppose Alice goes first. She can pick any uncolored vertex and color it with any of the colors. Then, Bob goes next. He also can pick any uncolored vertex and color it with any color, provided his choice of color is legal. He is not allowed to pick a color that would lead to an edge with both endpoints colored the same. The game is continued until the graph is completely colored or until some player is stuck. Alice wins if the she gets the graph colored completely and Bob wins if someone gets stuck.

One way to think about the game is there is an algorithm to four color every planar graph. The problem for Alice is Bob is not trying to help her. Thus, the game is like trying to color a planar graph with an adversary making ever other color choice. Given this view it is surprising to me there is a winning strategy for Alice when the number of colors are fixed—my guess would have been Bob could always mess up the coloring even with colors.The best known bound, to my knowledge, is due to Xuding Zhu:

Theorem: Every planar graph has

Here is the least number of colors Alice needs to win the game against any play by Bob. Earlier Hal Kierstead and William Trotter proved a bound of using previous insights on playing the game on forests. These results are quite surprising in my opinion, and I wonder if they can be used in complexity theory.

Packing Graphs

There is a beautiful result of Norbert Sauer and Joel Spencer, from 1978, about graph packings. Suppose and are two graphs on vertices. Say they pack provided there is a way to place their vertices onto the set so the resulting graph has no multiple edges. Their theorem is:

Theorem: Suppose and are graphs so that

Then, the graphs and pack; moreover, the packing can be found in polynomial time.

In the above theorem, denotes the maximum degree of the graph .

I mention this wonderful result because lately there has been quite a bit of work on extensions. Some look at other restrictions, some at extremal graphs, some at weaker notions of packing. See the paper by Kierstead and Kostochka for more details.

One of the most interesting results in their paper is a connection between packing and the coloring game I just talked about. Roughly, they show a connection between game playing and packing:

Theorem: If and are vertex graphs and

then and pack.

Here the game coloring number is an upper bound on : see their paper for the full definition. Their theorem is stronger than the classic Sauer-Spencer theorem, since

Another nice discussion of packing problems is the slides by Hemanshu Kaul. These slides state the long standing conjecture Bollobás-Eldridge Graph Packing Conjecture: if

then and pack. Packing problems are also related to complexity theory lower bounds—see this for an example.

Open Problems

There are many interesting open problems. An obvious one is to get the exact number of colors needed to win the coloring game on planar graphs, and on other families of graphs. Are there complexity theory applications of the coloring game? Also the packing problem is quite interesting. Are there other sufficient conditions which imply that two graph pack together?

[fixed typo]