# Discrete Hairy Ball Theorem

This question is inspired by

Math puzzles for dinner

The arrow compatibility conditions in that problem can be considered an attempt to discretize the notion of a continuous vector field.

The Hairy Ball Theorem states that there is no continuous nowhere vanishing vector field on the sphere, http://en.wikipedia.org/wiki/Hairy_ball_theorem.

We are led to the following formulation of a discrete Hairy Ball Theorem:

Instead of a sphere we will consider the squares lying on the surface of a 3 x 3 x 3 cube (Rubik's cube). Instead of searching for a continuous nowhere vanishing vector field, we ask if there exists a "legal configuration" of arrows on the squares of the cube?

A "legal configuration" consists of the following:

1) For any non-corner square, an arrow pointing in one of the eight cardinal directions is placed.

2) For any corner square, there is one cardinal direction which does not point to an adjacent square. For these squares, the placed arrow should point in one of the other seven directions.

The following conditions are modified from the original formulation:

3) Orthogonally adjacent non-corner squares should be compatible in the sense that if they are flattened to lie in a plane, the arrows should be at most 45 degrees apart.

4) Orthogonally adjacent corner squares should be compatible in the sense that if they are flattened to lie in a plane, the arrows are one rotation away from each other within the seven allowed directions. For example, if northeast is a prohibited direction on a corner square, then a northward pointing arrow on the square and an eastward pointing arrow on an adjacent square are compatible.

So, can you comb a hairy Rubik's cube? Does a legal configuration of arrows exist? What about an n x n x n cube?

-
might be obvious, but by just brute force experimentation you can't comb a 1x1x1 cube. – Otis Chodosh Aug 7 '10 at 6:41

By interpolating "legal configuration" if it were to exist, I think you can obtain a nowhere vanishing, continuous vector field on $S^2$. Suppose that for some $n$ there is a legal configuration on the $n\times n \times n$ cube. For each 1x1 face, put a vertex at the center. Then connect vertexes whose 1x1 face's touch. (basically something like a dual graph, but I don't know what the real terminology is).

Doing this, you get $(n-1)^2$ squares on each face of the Rubik's cube, $n-1$ squares on each edge of the Rubik's cube, and one triangle for each vertex of the cube. Now, put the arrow from the 1x1 face at the associated vertex. For each square or triangle we can now linearly interpolate to get a vector field over the whole thing. These will patch back together to form a continuous vector field on $S^2$ because on the lines they are glued along, the value on each piece is linear interpolation between the same two vectors. Thus, basically it remains to check that given a "legal configuration" you cannot interpolate to a zero vector.

The squares are not too bad, because the most that two of the vectors being interpolated can be off by is $90^\circ$, so you can't get a zero vector.

The triangles are a little trickier because things get twisted around, but if you try to write down the possible cases, you can see that there is basically only one type of "legal" corner configuration, and it doesn't interpolate to a zero vector.

This seems to show that you don't even need to assume anything special about corner squares, you can allow them to point in the 8th illegal position, and there are still no "legal configurations."

-
This does the trick! However, it would be nice to have a proof which does not depend on the continuous case... – Yakov Shlapentokh-Rothman Aug 7 '10 at 22:57
Yeah.. It seems like you could the discrete version to imply the continuous case by taking $n$ large enough you could choose a grid with arbitrarily small distance between adjacent points so that if you let each point have the cardinal direction closest value of the vector field at that point you would still have at most $45^\circ$ difference between adjacent arrows.. – Otis Chodosh Aug 8 '10 at 2:51

I am not sure I fully understand the question, but you should know the following classical discrete version of the hairy ball theorem:

Let $P \subset \Bbb R^3$ be a convex polytope. We say that an orientation of edges of $P$ is balanced if every vertex has at least one ingoing and one outgoing edge (i.e., the oriented graph has no sinks and no sources). Then the edges of at least two faces of $P$ form oriented cycles.

The proof is completely straightforward and goes exactly the way you think it should go (follow the arrows!). This result has been rediscovered a number of times. The earliest place where I found this result is here: L. Glass, A combinatorial analog of the Poincaré index theorem, J. Combin. Theory Ser. B 15 (1973), 264–268. See also Ex. 25.15 in my book for the context, and connections with other related results (sorry for the self-promotion).

-
That does indeed seem extremely relevant! I will have to think about it a bit, but my hunch is that non-existence of a "legal configuration" follows without much work from this theorem. – Yakov Shlapentokh-Rothman Aug 7 '10 at 5:48
@Pak. Can we deduce the continuous version of the Hairy ball theorem from the discrete version, by some limiting process ? – coudy Aug 7 '10 at 14:18
@coudy: check out Thurston's "Three-dimensional geometry and topology", pages 19--25. It's not a limiting process, but rather showing that any vector field can be taken "transverse" to the edges of some triangulation (=convex polytope). – Tom Church Aug 7 '10 at 16:32