The solutions are in! This problem of the week was interesting for me: the usual pattern has been that I pose problems that I’ve solved myself at some point in the past, giving me a kind of “inside edge” on understanding the solutions that come in. But, as I said in POW-12, the difference this time is that the solution I knew of came from someone else (Arin Chaudhuri). What was interesting for me — and given the circumstances, it was probably inevitable — is that some of the solutions we received forced me to make contact with some mathematics I’d only heard about but never studied. Let me get to that in a minute.

Another interesting thing for me — speaking now with my category theorist’s hat on — is how utterly simple and conceptual Arin’s proof was! I was pleased to see that regular problem solver Philipp Lampe also spotted it. Wait for it…

*Solution I by Philipp Lampe, University of Bonn*: The answer is 8.

Among the eight neighbors of an arbitrary vertex, all colors of an admissible coloring must occur. Thus, 8 is an upper bound for the maximum number of colors one can use. We have to show that there is an admissible coloring with eight colors.

The vertices of the 8-dimensional cube may be represented by vectors with in , in other words as vectors in , the 8-dimensional vector space over the field with two elements (i.e., the integers modulo 2). Two such vectors are neighbors iff their coordinate vectors differ in exactly one place, in other words if considered modulo 2, where is one of the eight standard basis elements (with -th coordinate 1, and the other coordinates 0).

Now let our “colors” be the 8 elements of , the 3-dimensional vector space over . Let the vertex “coloring”

be the unique -linear map such that ; that is, define the color of a vertex/vector by

Now, if is any vector, the colors of its neighbors are . The colors of these neighbors are all distinct since the are distinct. Hence all 8 colors are represented among the colors of the neighbors of any given vertex , QED.

What I love about this solution it is how *natural* it is. I’ll say a little more about this in remarks below.

But I also learned a thing or two by studying the next solution. It relies on the theory of Hamming codes, with which I was not conversant. Up to some small edits, here is exactly what Sune Jakobsen submitted:

*Solution II by Sune Jakobsen (first-year student), University of Copenhagen*: Since each vertex only has 8 neighbors, the answer cannot be greater that 8.

Now we construct such a coloring with 8 colors. An 8-dimensional cube can be represented by the graph with vertices in , and with an edge between them iff the Hamming distance between them is 1. We color a vertex with color 8 if the seven first bits in the vertex is a “correct” Hamming message (cf. Hamming code (7,4)), and color it in color if the first seven bits give a correct Hamming message upon changing bit . This is a well-defined coloring, since each element in is either a correct Hamming message, or is Hamming distance 1 away to exactly one correct Hamming message.

It remains to show that no vertex is neighbor to two vertices of the same color. The Hamming distance between these two vertices is 2, thus the Hamming distance between the first 7 bits of two neighbors must be 1 or 2. If two neighbors had the same color , then by definition one would get two correct Hamming messages by changing bit in both of them, and the Hamming distance between these messages would be the same as before — either 1 or 2. But the distance between any two correct Hamming messages is at least 3. Contradiction.

**Remarks:**

1. Let me give a little background to Sune’s solution. Mathematically, the Hamming code called “(7, 4)” is the image of injective linear map

given by the matrix

1101

1011

1000

0111

0100

0010

0001

The Hamming code is what is known as an “error-correcting code”. Imagine that you want to send a 4-bit message (each bit being a 0 or 1) down a transmission line, but that due to noise in the line, there is the possibility of a bit being flipped and the wrong message being received. What can you do to help ensure that the intended message is received?

The answer is to add some “parity check bits” to the message. In the code (7, 4), one adds in three parity checks, so that the transmitted message is 7 bits long. What one does is apply the matrix to the 4-vector, to get a 7-vector (remember we’re working modulo 2), and this 7-vector is sent down the line. Assuming only a moderate amount of noise in the transmission line, perhaps the 7-bit message will remain intact or perhaps a single bit will be flipped, more rarely two bits will be flipped (and we’ll assume the event that more than two are flipped has negligible probability). Now, the Hamming encoding is rigged up so that if the 7-bit vector is received as sent, then the parity checks will report 0 errors. If the parity checks report an error, they report precisely where the error occurred if the received vector was off by one bit. (If two flips occurred, then the receiver can still detect from the parity checks that an error occurred. The parity checks can never detect how many bits were flipped, but if the receiver assumes correctly that just one bit got flipped, he can restore the intended message with accuracy. If three or more got flipped, then the receiver got the wrong message, but he would never know it if the parity checks reported back 0 errors.)

How does this work? By having the receiver apply a parity-check matrix to the received message, given by the matrix

1010101

0110011

0001111

In the first place, , and so if the message received belongs to the image of (is a “correct Hamming message” in the terminology of Solution II), which will indeed be the case if there were no errors in the transmission, then applied to the message will produce the zero vector. In the case where one bit got flipped in the transmission, applied to the received vector will return a nonzero 3-vector, but the beauty of the Hamming code is that the 3-vector will spell out in binary the bit the error occurred (for example, if the output vector is , then error occurred in the bit with binary number 011, that is bit 3). In that case, the receiver flips that bit to restore the original message. In these two cases, the original 4 bits are then read off as the 3rd, 5th, 6th, and 7th coordinates of the (possibly corrected) 7-vector.

By the way, Sune reminded us that Hamming codes also came up in a post by Greg Muller over at The Everything Seminar, who used the existence of a Hamming code in every dimension to solve general hat-guessing puzzles.

2. Within minutes of posting the original problem, we received a message from David Eppstein, who reported that the solution of 8 colors is essentially contained in a paper he coauthored with T. Givaris (page 4); his solution is close in spirit to Sune’s.

Arin Chaudhuri also surmised the connection to Hamming codes, and mentions that the problem (in a slightly different formulation) originally came from a friend of a friend, who blogs about a number of related problems on this page. Presumably the author had things like error-correcting codes in mind.

3. Sune and David noted that their solutions generalize to show that on the -dimensional cube (for any ), it is possible to color the vertices with colors (the maximum number possible) so that all of the colors show up as colors of the neighbors of any given vertex.

This is very easy to see by adapting Philipp’s method. Indeed, for each just take the color set to be the -vector space . The set of vertices of the -dimensional cube may identified with the -vector space generated by the set (as basis), and the desired coloring is then just the -linear map that extends the identity function on . As mathematical constructions go, you can’t get much more canonical than that! No fuss, no muss — it’s a purely categorical construction (categorists call it a counit of an adjunction). So then why didn’t I see that myself? 🙂

4. We’re still not sure what the story is in other dimensions. If is the maximum number of admissible colors in dimension , then about all any one of us knows right now is that for , is weakly monotone increasing, and that if is not a power of 2. There’s a conjecture afloat that where is the floor function, but for now that should be treated as a wild guess. If anyone has further information, please let us know!

Solved by Arin Chaudhuri, David Eppstein, Sune Jakobsen, and Philipp Lampe. Thanks to all those who wrote in!

## 22 comments

Comments feed for this article

January 4, 2009 at 7:57 am

hilbertthm90I’m not sure if any readers are familiar with the book “The Probabilistic Method” by Alon and Spencer, but now that I see that bound guess, I really think I’ve seen it before and my only guess would be in that book. I don’t own a copy. I may be able to find one somewhere, but if anyone has it, is this problem in there? If not, is there a similar enough problem that the method can be adapted?

The basic idea, I think (it’s been awhile), would be to show that randomly coloring a hypercube with that many colors has strictly positive probability of satisfying the given property. Don’t quote me on that, though.

January 4, 2009 at 9:27 am

Sune Kristian Jakobsen“If the received vector is off by one bit, then the parity checks will report where the error occurred and the receiver makes a correction accordingly. (If two bits got flipped, the receiver will not be able to correct the received message with certainty, but will at least be aware that an error occurred…)”

If two bits got flipped, the receiver will think, that it was a third bit that got flipped, and he will “correct” the message to a wrong message. If the message you get is not a correct Hamming code, there is no way to tell how many bits that got flipped, so you have to choose either to: Detect and correct any one bit flip OR detect any one or two bit flip.

If you find out anything about the n-dimensional problem, please tell me!

January 4, 2009 at 1:11 pm

Todd Trimblehilbertthm90: from what you say, it sounds like they give a proof that is a

lowerbound (which we already know). To show what we’d really like, that it is also an upper bound, means you have to rule out the possibility of using more colors, and I don’t see how a probabilistic proof would be able to do that. (That’s not to say that the lower bound result using a probabilistic proof wouldn’t be interesting.)Sune: yes, I put that badly (not literally wrong, but the ‘with certainty’ is obviously misleading). Let me fix it up that bit, which occurs just before “if three or more got flipped…” — thanks!

January 4, 2009 at 3:44 pm

Sune Kristian JakobsenIn 7 dimensions, you only need to color 24 vertices in order to color a neighbor to each vertex. Color all vertices whose first 6 bits is one of the following sequences:

000000

000101

001110

010011

010100

011001

100110

101011

101100

110001

111010

111111

In 7 dimensions we’ve got 128 vertices, so if we only need 24 vertices in each color, it could be possible to use 5 colors. After finding this example, I lost my confidence in the -conjecture.

January 5, 2009 at 12:16 am

Todd TrimbleWell, there wasn’t much cause for confidence in this conjecture in the first place, since it’s the strongest possible conjecture one could make, given what we know!

I sort of see what you’re driving at with this back-of-the-envelope counting argument, and why it would weaken confidence in the conjecture. There are conceivably some constraints embedded in the structure of the Hasse diagram which we’re not seeing but which would somehow obstruct a 5-coloring of the 7-cube, but admittedly my intuition is in the dark here.

My only vague thought (besides programming a computer to help attack this problem, which I don’t feel equipped to do myself) is to try to exploit somehow the Boolean algebra structure on the power sets (like P(7)) that we’re dealing with. The fact that we get the “best possible” answer in the case P(2^k) might have something to do with the fact that those are

freeBoolean algebras; the fact that Venn diagrams keep popping up in that Wikipedia article on Hamming codes does seem somehow suggestive to me of a Boolean algebra approach. (I wish I had more insight into this Hamming code business!)January 5, 2009 at 7:56 pm

Sune Kristian JakobsenI third approach to the 8-dimensional problem:

Observe, that if you color the 7-cube in 8 colors, such that for each vertex v and color c, either v is c or one of the neighbors of v are c, we are done: We simply made the 8-cube of two copies of the 7-cube. (like my above comment, so the color of v only depends on the first 7 bits).

Now I want to color some of the vertices, such that each vertex is either colored or neighbor to a colored vertex (I use a “greedy algorithm”): I want this to be true for 0000000, so I color 0000000. Now every vertex with only one 1 is a neighbor to a colored vertex. Next I want to color some vertices with three 1’s so that every vertex with two 1’s is a neighbor to a colored vertex. This problem is solved by the Fano plane: The point in the plane correspond to the bit numbers, and the lines correspond to strings: {1,2,4}1101000. Now we have colored 8 vertices. For each colored vertex color the opposite vertex. It turns out, that this colorings works. Let the colors be the elements of , and let the used color be (000). Color vertex v in color c if v+c is colored in color (000). This coloring is well defined and gives the same coloring as the two other approaches.

It seems to be harder to generalize to other dimensions, but perhaps block designs could be useful on order to construct a counter example (if it exists).

Sorry if this comment was trivial, but I hadn’t thought about the connection to the Fano-plane before.

January 9, 2009 at 7:27 pm

Sune Kristian Jakobsen.

Proof:

Let be the function from elements v in to the parity of the number of 1’s in v. Let and be colorings such that each vertex is neighbor to a vertex in each color. Then the same is true for the coloring given by .

Of course, since we already have the inequality , it is unlikely that a “tensor-trick”-like argument would give any new information, but I thought the proof was worth sharing.

January 21, 2009 at 2:54 am

notedscholarHasn’t this problem already been solved?

January 21, 2009 at 3:05 am

Todd TrimbleWell, maybe, but we haven’t heard anything. Do you have something to add to this discussion?

February 4, 2009 at 8:18 am

The tesseract flattened « crystalmath[…] tesseract flattened By crystalmath A problem-of-the-week in Todd and Vishal’s blog led me to the following two-dimensional view of the tesseract […]

February 11, 2009 at 5:23 pm

Sune Kristian JakobsenThe original problem was:

What is the maximum number of colors you could use to color the vertices of an n-dimensional cube, so that starting from any vertex, each color occurs as the color of some neighbor of that vertex? (1)

This can be reduced to a problem in n-1 dimensions:

What is the maximum number of colors you could use to color the vertices of an (n-1)-dimensional cube, so that starting from any vertex, each color is the color of the vertex or occurs as the color of some neighbor of that vertex? (2)

This is because the n-cube is a bipartite graph: If you can find a coloring of the n-cube that obeys (1), you can throw away the vertices with an odd number of 1’s, and then removed the last bit of every vertex. This gives a coloring of the (n-1)-cube, that obeys (2). On the other hand, if you have a coloring of the (n-1)-cube, that obeys (2), you can take two copies of the cube and you’ll get a coloring of the n-cube that obeys (1).

I have written a program that looks for such colorings. This shows that , but it would probably take hundreds of years to prove that (using my program, at least. Perhaps someone else can do better?) .

Define a partial coloring of the (n-1)-cube to be a coloring of the first b vertices of the (n-1)-cube, such that for every vertex v, there exist a coloring of the rest of the vertices, such that each color is the color of v or occurs as the color of some neighbor of v. Here “first” is with respect to the coloring you get by considering the vertices as numbers in binary: e.g. 0000, 0001, 0010, 0011, 0100,…

Now, my program shows that there exists a partial coloring of 26 vertices of the 5-cube in 5 colors, but no partial coloring of the first 27 vertices. So if we want to find at simple proof that no such coloring exists, we can’t just look at some small subset of the vertices. The program has also found a partial coloring of 55 vertices of the 6-cube in 5 colors.

If anyone has any idea on this problem, I would be happy to hear about it. But otherwise, I probably won’t work on this problem anymore.

February 19, 2009 at 1:05 pm

The tesseract flattened « crystallomath[…] tesseract flattened By crystalmath A problem-of-the-week in Todd and Vishal’s blog led me to the following two-dimensional view of the tesseract […]

March 5, 2009 at 8:28 pm

Sune Kristian JakobsenI have found some literature about the problem. First some terminology:

A set of vertices, such that every vertex in G not in the set, is a neighbor to a vertex in the set, is called a “dominating set” for the graph.

A set of vertices, such that every vertex in G is a neighbor to a vertex in the set, is called a “total dominating set” for the graph.

In the original problem we want to find as many pairwise disjoint total dominating sets as possible in the n-cube and in the reduced problem mentioned above, we want to find as many pairwise disjoint dominating sets as possible in the (n-1)-cube. A partition of the vertices V into dominating sets is called a domatic partition (domatic is made from the two words dominating and chromatic). The maximal size of the domatic partition of a graph G is called the domatic number of G. Now, a_n is just the domatic number of the (n-1)-dimensional cube, and this problem have been studied.

Bohdan Zelinka once conjectured that a_n=n-1 (I have translated the conjcture to the terminology used in the post) when n is not a power of two. I think this was disprove in “On the domatic number of the n-cube and a conjecture of Zelinka” (http://portal.acm.org/citation.cfm?id=38255). I don’t understand french, but I think they just used a formerly know fact in a trivial way. In the same paper it was conjectured that a_n/n -> 1 as n-> infinity.

It seems that the only known values are a_n and a_(n+1) where n=2^k and a_6=4.

Another interesting article: http://www.sciencedirect.com/science/article/B6TYJ-46NX3N5-7J/2/2bf5ce5915d212229fa55773bf468a83

March 5, 2009 at 9:03 pm

Todd TrimbleSune — thanks very much. You’ve given us all these great comments, and I’ve been feeling a little guilty about not responding to them.

Wow. So not even a_7 is known. This makes me suspect that the problem must be pretty hard.

That’s interesting.

I’ll have to look at those articles you cited. But thanks very much for all this thought and research!

March 7, 2009 at 4:28 pm

Sune Kristian JakobsenThis article:

http://www.ingentaconnect.com/content/ap/ej/1997/00000018/00000003/art00093

claims to have proved that . A text-version of the article can be found here:

http://nzdl.sadl.uleth.ca/cgi-bin/library?e=d-00000-00—off-0cstr–00-0–0-10-0–0-0—0prompt-10—4——4-0-1l–11-en-50-0–20-about–100-0-1-00-0-0-11-1-0utfZz-8-00-0-1-00-0-0-11-1-0utfZz-8-00&d=HASH01221e80b0a00f3094f036bc.14&cl=CL1.260&gp=1

but the mathematics in the text-version is almost impossible to read.

Obviously, this result contradicts the conjecture that .

March 7, 2009 at 8:58 pm

Sune Kristian JakobsenThe article

http://www.ingentaconnect.com/content/ap/ej/1997/00000018/00000003/art00093

claims to prove that as . I have found a text-version of the article here:

http://nzdl.sadl.uleth.ca/cgi-bin/library?e=d-00000-00—off-0cstr–00-0–0-10-0–0-0—0prompt-10—4——4-0-1l–11-en-50-0–20-about–100-0-1-00-0-0-11-1-0utfZz-8-00-0-1-00-0-0-11-1-0utfZz-8-00&cl=CL1.260&d=HASH01221e80b0a00f3094f036bc.4>=2

but unfortunately the math is almost impossible to read in this file. The same article proves that .

March 8, 2009 at 6:11 pm

Todd TrimbleSune Jakobsen wrote to say that the claim as , given in the paper he previously cited, of course refutes the conjecture I made that (as does of course the claim ).

But it seems these are rather non-trivial problems. Many thanks to Sune for digging up the references.

September 10, 2009 at 6:31 pm

Kifayat ullahI am so tried to drawing a graph of 7colors by partition method but does not success. please help me in this question. Thanks you

September 10, 2009 at 10:58 pm

Todd TrimbleKifayat, I’m not sure what you’re trying to ask, but in the solution it is stated that it is possible to color the vertices of the 8-dimensional cube with

8colors so that for each vertex v and each color, there is some vertex adjacent to v with that color.Maybe I can express the solution a little differently using the concept of Nim-sums. Let’s imagine that the vertices are represented by octuplets where each is either 0 or 1. To specify such a vertex , it’s enough to give the set .

Let’s write elements in binary form, and let’s choose 8 colors . Then, the idea is to color the vertex with the color if

where you take the Nim-sum of the ‘s in their binary representation.

For example, consider the vertex . Here the coordinates are , and so on. The coordinates where I see a 1 are at 2, 4, 6, and 7. Write these in binary: 010, 100, 110, 111. Add them up Nim-wise (meaning no carries): we get 111, which represents 7. That tells me to color the vertex with the color . Color all the vertices by following this recipe.

Now I claim that at every vertex, each color is represented at some neighboring vertex. For example, for the above example , how would I find a neighboring vertex colored ? (Neighboring means that and differ in only one coordinate.) Easy: the color of is , the color of is to be , I Nim-subtract 7 – 3 = 111 – 011 to get 100 which represents 4, so I just change the coordinate to 0 to get . Thus has color , as you can check by following the recipe described above.

Hope this was clear.

November 27, 2011 at 9:21 pm

family living erbjudandeI de flesta fall kommer du att gå med det andra alternativet eftersom du litar på vad du kan åskåda med egna eyes.

gratis prov

När allt uppfostra småttingar som ensamstående förälder är dyrt därtill det var ofta inte mycket kvar att köpa dator tillhörande programvara jämte andra skuld till.

May 7, 2019 at 7:46 pm

prof dr mircea orasanulook a problem indeed

March 16, 2021 at 3:50 am

Wayne J. MannI came across this blog because I made the same conjecture (a_n always a power of 2) back in 2005 and thought it was finally time to see if anyone had come up with a solution. In case anyone else comes here for the same reason, and as the links above are now broken, I thought I would post a solution. In hindsight it is the most obvious approach to take, but I see from the above conversation that I am not the only one who was stumped by it. The method is from the 1997 Patric Ostergard paper, that was presumably linked to above.

So the issue is that binary is a very efficient way of communicating a number between 1 and 64, but less efficient at communicating a number between say say 1 and 49. However using 7-ary digits is efficient for communicating a number between 1 and 49. It was noted several times in this blog that the solution to the original problem can be expressed in terms of Hamming codes, and thus works for q-ary digits for any prime power q.

In particular, given |P^2(F_7)|=8 7-ary digits, by changing at most one you can communicate a number between 1 and 49.

From the original problem we know that given 7 bits, you can communicate any 7-ary digit by flipping at most one bit. Thus replace each 7-ary digit with 7 bits to get 7*8=56 bits and you can communicate a number between 1 and 49 by flipping at most one bit.

Finally add a dud bit, to change if you do not need to flip anything, and we have a_{57} is at least 49, disproving the conjecture.