Feature Column from the AMS

Cubes

5. A recursive way of constructing cubes

There is a delightfully simple way of constructing an (n+1)-dimensional cube from two copies of the cube in n dimensions. Draw two copies of, say, an n-cube, and now join corresponding vertices. What one has is a drawing of a (n+1)-cube.

One can think of the construction of the familiar 3-cube as being done in this manner from the even more familiar 2-cube, the square. The diagram below shows the two squares in black and the edges which join the corresponding vertices in red.

To emphasize that this construction is to be considered combinatorial in nature the two "squares" need really be only 4-gons and they need not be the same size.

This construction can be repeated to construct a combinatorial 4-cube:

Figure 1

and 5-cube:

Figure 2

Note the rather different impression that different drawings can give of the same structure. Thus, one can think of the 16 vertices to the left in the drawing of the 5-cube above as a 4-cube (Figure 3, below), but it creates a rather different visual appearance than the initial 4-cube (Figure 1) that was shown.

Combinatorial versions of the higher dimensional cubes proved useful in showing that the Simplex Algorithm for Linear Programming was not a polynomial time algorithm. This was accomplished by using what are now known as the Klee-Minty Cubes (1972), discovered by Victor Klee and George Minty. These polytopes produced by Klee and Minty require that the standard version of the simplex method run through all of the 2ⁿ vertices of an n-dimensional cube in order to find the optimal value of a linear programming problem.

Figure 3

The importance of having different representations of the same object is that these different representations often suggest different questions for future research. Whereas Figure 1 might suggest questions about how many 3-cube faces there are in a 4-cube or questions about "perspective," the drawing in Figure 3 may suggest a question such as what drawing of a 4-cube in the plane has the fewest crossings of edges at points which are not vertices of the cube? (i.e. What is the crossing number of a 4-cube?)