Feature Column from the AMS

Cubes

4. Combinatorial perspectives on cubes

While most people think of cubes as metrical objects, all the sides of the cube having the same length, mathematics has shown that cubes are important as combinatorial objects as well. When viewing a cube metrically, there are two commonly used approaches. The first approach gives the coordinates of the points that are the vertices of the cube. For the 3-cube these coordinates, suppressing the parentheses and commas that are usually used, are: 000, 100, 110, 010, 001, 101, 111, and 010. The line segments defining the edges of the cube that join these vertices are chosen so that two vertices are joined by an edge if and only if they differ in one position. Thus, the neighbors of 111 on the cube are 011, 101, and 110.

What is the Euclidean distance between two vertices of the 3-cube joined by an edge? Using the usual distance formula, we see that the edges have length 1. However, it was Richard Hamming (1915-1998) who realized that the more pragmatic description above, of counting the number of positions in which binary sequences differed could be used as a distance, too. This distance is known today as the Hamming distance or Hamming metric. For example. the Hamming distance from 011 to 100 is 3, from 001 to 111 is two, while from 110 to 111 is 1. The only pair of these three that is joined by an edge of the cube is the last. Thus, the distance between the vertices of the 3-cube with these coordinates is 1 in both the Hamming distance and the Euclidean distance! Since the Hamming distance is a distance function like any other, one can talk about the points which have a particular fixed distance from a vertex of a d-cube in the Hamming metric. I will refer to these as spheres. In fact, the observation that the sphere of radius 1 centered at 000 and the sphere of radius 1 centered at 111 have no points in common is the basis for the fact that one can use 000 and 111 as an error correction code with two code words. These code words could be used to code two colors, say black and white. The famous code that Hamming first discovered in his pioneering work on error correction consisted of 15 binary sequences of length 7. These sequences correspond to vertices on the 7-cube whose spheres of radius 1 are disjoint. Thus, they represent a relatively large collection (15 elements) of short strings (length 7) that will correct a single error.

The other standard approach is to define the 3-cube by the inequalities:

0 ≤ x_i ≤ 1

where subscribed variables are used instead of the usual x, y, and z. This view of the cube clearly shows that for the d-cube there are d pairs of hyperplanes (the higher dimensional analogue of planes) which are parallel and which are perpendicular to all the others. It is this last perpendicularity condition that challenges the visual imagination for understanding even the 4-cube. Whereas everyone can visualize the three segments at the corner of a 3-cube as being mutually perpendicular, most people have no way to "see" four segments at the corner of a 4-cube as mutually perpendicular. Is there some way at least of drawing a diagram that helps us think about the 4-cube? Perhaps surprisingly, by converting to a combinatorial viewpoint, drawing 4-cubes, 5-cubes, etc. becomes a snap!