An interesting connection between a game on graphs and packing graphs together

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 ${6^{th}}$—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 ${G}$ and a number of colors ${k}$. Suppose Alice goes first. She can pick any uncolored vertex and color it with any of the ${k}$ 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 ${O(\log n)}$ colors.The best known bound, to my knowledge, is due to Xuding Zhu:

Theorem: Every planar graph ${G}$ has ${\chi_{g}(G) \le 17.}$

Here ${\chi_{g}(G)}$ 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 ${33}$ 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 ${G}$ and ${H}$ are two graphs on ${n}$ vertices. Say they pack provided there is a way to place their vertices onto the set ${\{1,2,\dots,n\}}$ so the resulting graph has no multiple edges. Their theorem is:

Theorem: Suppose ${G}$ and ${H}$ are graphs so that

$\displaystyle \deg(G) \deg(H) < n/2.$

Then, the graphs ${G}$ and ${H}$ pack; moreover, the packing can be found in polynomial time.

In the above theorem, ${\deg(G)}$ denotes the maximum degree of the graph ${G}$.

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 ${G}$ and ${H}$ are ${n}$ vertex graphs and

$\displaystyle (\text{gcol}(G)-1)\deg(H) + (\text{gcol}(H)-1)\deg(G) < n$

then ${G}$ and ${H}$ pack.

Here the game coloring number ${\text{gcol}(G)}$ is an upper bound on ${\chi_{g}(G)}$: see their paper for the full definition. Their theorem is stronger than the classic Sauer-Spencer theorem, since

$\displaystyle \text{gcol}(G) -1 \le \deg(G).$

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

$\displaystyle (\deg(G) + 1)(\deg(H) + 1) \le n+1,$

then ${G}$ and ${H}$ 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]

1. May 1, 2010 2:49 pm

I think that the Bollobas-Eldridge conjecture was recently solved by Gabor Kun, except for finitely many cases, see April 8th here:
http://www.math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math

May 2, 2010 7:44 am

Thanks for the pointer.

2. May 1, 2010 9:12 pm

hanks it helped alot to clear some stuff about games.

3. May 2, 2010 3:04 pm

The following talk gives a more thorough introduction to graph packing questions than the link above:
http://www.math.iit.edu/~kaul/talks/GraphPackingTalk-long.pdf

Bollobas’ Extremal Graph Theory textbook from 1978 (recently reissued by Dover) has a chapter on Graph Packing and its application to complexity theory.
Also look up Lovasz’ lecture notes at http://arxiv.org/PS_cache/cs/pdf/0205/0205031v1.pdf and the chapter on “Lower bounds on Randomized Decisions Trees”.

For more Graph Packing problems, see “Wozniak, M. (1997) Packing of graphs. Dissertationes Math. 362, 78 pp.” Unfortunately its not available online.

The news about Kun’s solution of the Bollobas-E-C conjecture came out last Fall. Eagerly waiting for the paper.

• May 3, 2010 3:09 am

http://rsa2009.amu.edu.pl/abstracts/Gabor_Kun.pdf
(although the abstract only mentions the asymptotic version, by the time of the conference he already had and talked about the full version)

4. May 4, 2010 4:18 pm

Don’t forget tree packing conjecture (Problem 25) of Gerhard Ringel (1963).

See

http://www.combinatorics.org/Surveys/ds6.pdf

5. May 7, 2010 2:42 am

I like this game a lot.

6. May 9, 2010 2:35 am

There is a strange open problem concerning this game, due to Xuding Zhu. Suppose Alice wins on a graph G with k colors. Is it true that she wins on G with k+1 colors? This looks like a stupid question, as, intuitively, the more colors in the game – the better for Alice. But notice that this allows also more freedom for Bob… Here is a nice survey on this game:

http://www.math.nsysu.edu.tw/~zhu/papers/game/monthly793-803-grytczuk.pdf

There is another graph coloring game, which is even more mysterious. In this variant Alice only points on a vertex while Bob is choosing a color. The goals of the players are as before: Alice tries to color the whole graph, while Bob is trying to get stuck. Clearly, for bipartite graphs Alice wins with two colors, but there are 3-chromatic graphs for which 4th color is needed. Of course, col(G) colors are sufficient, but it is not known if there is any general bound in terms of chromatic number.

If additionally we impose a condition that a colored part of a graph must be connected (at any moment of the game), then there is a graph for which Alice wins with 3 colors, but looses with 4 colors :).