Rainbow Graphs
I gave you the Wise Men Without Hats puzzle in one of my previous posts:
A sultan decides to check how wise his two wise men are. The sultan chooses a cell on a chessboard and shows it to the first wise man. In addition, each cell on the chessboard either contains a pebble or is empty. The first wise man has to decide whether to remove one pebble or to add one pebble to an empty cell. Next, the second wise man must look at the board and guess which cell was chosen by the sultan. The two wise men are permitted to agree on their strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?
My readers solved it. The solution is the following. Let us assign a number between 0 and 63 to every cell of the board. The second wise man takes numbers corresponding to cells with pebbles, converts them to binary and XORs the result. The answer is the cell number that he is seeking. The first wise man can always add or remove a pebble to make the XORing operation of the remaining pebbles produce any given number from 0 to 63.
This solution only works for boards that have a power of two as the number of cells.
Let’s look at the solution more closely. Let us create a graph corresponding to this problem. The vertices of the graph will correspond to the positions of pebbles. That means vertices are in one-to-one correspondence with the subsets of the set of 64 elements. Let us connect two vertices if we can get from one position to another by removing or adding a pebble. That means vertices are connected if two corresponding sets differ by exactly one element. We can see that the resulting graph is regular and each vertex is connected to exactly 64 other vertices.
Let us assign one out of 64 colors to each cell of the chessboard. The second wise man can guess the cell by looking at the chessboard. From this we can conclude that there is a bijection from the vertices of the graph to chessboard cells. In other words, we can color the graph in 64 colors. The existence of the strategy for wise men means that we can color the graph in such a way that each vertex is connected to the vertices of all colors.
As each vertex in our graph has exactly 64 neighbors, the graph has the following property: It can be colored in 64 colors in such a way that every vertex is connected to exactly one vertex of every color.
As soon as I realized that there is such a graph-theoretical object, I started to run around MIT asking everyone if such objects were studied or have a name.
It appears that indeed such an object has a name. A graph that can be colored into k colors in such a way that every vertex has exactly one neighbor of every color is called a rainbow graph.
Andrew Woldar discusses properties of such graphs in his paper. In particular, rainbow graphs are matching graphs. Indeed, every vertex is connected to exactly one vertex of the same color. Hence there is a natural pairing on vertices. From here, we can conclude that the smallest size of a rainbow graph is 2k.
Several MIT students liked the wise men problem and the associated graph object so much that they decided to study them. Hwanchul Yoo, SuHo Oh, and Taedong Yun enumerated all rainbow graphs of size 2k. The number of non-isomorphic rainbow graphs of size 2k equals mitthe number of switching classes of graphs with k vertices. The corresponding sequence A002854 starts as: 1, 1, 2, 3, 7, 16, 54. The paper is soon to appear. It is titled “Rainbow Graphs and Switching Classes.”
Share:
misha:
Clever… any solutions for not power of 2 board?
30 April 2010, 11:04 amAnimesh:
I seem to find an ambiguity in this problem. Why not just place a pebble on the chosen cell and remove all other
pebbles? There is no constraint mentioned in the problem that this method can’t be the predecided approach.
The binary number method is applicable to one of similar problems
1000 Bottles of wine are there and one of them is poisoned. You have N people to find the poisoned bottles. Basically N will die. Assuming that they will die within 1 hour after drinking. How can you minimize N and what will be the minimum N?
26 May 2010, 7:33 amTanya Khovanova:
Animesh,
You can move exactly ONE pebble.
26 May 2010, 8:23 amAnimesh:
Oops….Sorry I missed that. Thanks for the clarification.
26 May 2010, 12:24 pmDoc:
Hi Tanya! It is I, Andrew. I came upon your blog quite by accident. I so admire you and your limitless energy. You are a very talented ambassador and communicator of our beloved subject. Keep up the good work! [Note: I actually coined the term “rainbow graph” in that paper, and I am actually relieved to learn that it is gaining acceptance. (Apparently it has quite different meanings in other fields, e.g., mathematical physics and computer science.) I also here mention that the “affine part” of the regular generalized triangles, quadrangles and hexagons are further examples of rainbow graphs, as are the doubly infinite family of graphs constructed by Lazebnik, Ustimenko and me in “A new series of dense graphs of high girth,” Bulletin of the AMS 32 (1) (1995), 73-79. These latter graphs were initially constructed as extremal objects but have since found their way into coding theory and cryptography.]
15 August 2010, 12:11 pmTaedong:
Our paper is now on the arXiv. https://arxiv.org/abs/1108.6143
31 August 2011, 8:35 pmSorry for procrastinating it for too long. 🙂