Happy holidays, folks! And happy birthday to Topological Musings, which Vishal started just a little over a year ago — we’ve both had a really good time with it.

And in particular with the Problem of the Week series. Which, as we all know, doesn’t come out every week — but then again, to pinch a line from John Baez’s This Week’s Finds, we never said it would: only that each time a new problem comes out, it’s always the problem for *that week*! Anyway, we’ve been very gratified by the response and by the ingenious solutions we routinely receive — please keep ’em coming.

This problem comes courtesy of regular problem-solver Arin Chaudhuri and — I’ll freely admit — this one defeated me. I didn’t feel a bit bad though when Arin revealed his very elegant solution, and I’d like to see what our readers come up with. Here it is:

What is the maximum number of colors you could use to color the vertices of an 8-dimensional cube, so that starting from any vertex, each color occurs as the color of some neighbor of that vertex? (Call two vertices *neighbors* if they are the two endpoints of an edge of the cube.)

Arin, Vishal, and I would be interested and pleased if someone solved this problem for all dimensions .

Please submit solutions to **topological[dot]musings[At]gmail[dot]com** by **Friday, January 2, 2009**, 11:59 pm (UTC); do **not** submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.

### Like this:

Like Loading...

*Related*

## 4 comments

Comments feed for this article

December 27, 2008 at 3:12 am

Rod CarvalhoTodd,

IMHO, the problem statement is a bit sketchy. The problem sounds quite interesting, but I don’t get what exactly is being asked.

The only thing I understood is that we have an -dimensional cube whose vertices we would like to color with colors. We would like to maximize given the constraint that the colors of a vertex and the colors of its neighbors obey some conditions. I don’t understand what the conditions are.

Could you please, pleeeease rephrase the problem in rigorous terms? Many thanks in advance.

December 27, 2008 at 4:18 am

Todd TrimbleI honestly thought it

wasrigorously stated (and I fancy myself as generally pretty careful when I discuss mathematics). But I’ll say it more formally now:Let be a set whose elements we’ll call “colors”. An –

coloringof a set is a function . Let now be the set of vertices of an 8-dimensional cube, and define the neighborhood relation by if and only if and are distinct and there exists an edge of the cube that both and are incident to.Now consider the following condition on a coloring :

What is the maximal cardinality of a set for which there exists a coloring satisfying this condition?

Let me know if the problem is still unclear.

December 27, 2008 at 4:32 am

Rod CarvalhoTodd,

I didn’t mean to offend anyone. I just found the original problem statement slightly ambiguous. It would have been silly to dedicate some of my time to solving a problem which is not the one you proposed. Now that you’ve written the problem statement formally, all ambiguity has been removed. Thanks.

December 27, 2008 at 4:41 am

Todd TrimbleNo offense taken. I’ll concede that the problem statement was tersely put, so it’s probably good that you asked.