Hypercube Models via Genus Embeddings

Year: 2024 Authors: Richard H. Hammack

Core claim

Genus embeddings of hypercube graphs provide 3D models that make high-dimensional cube structure easier to visualize and understand.

Topics

hypercube visualization, graph embeddings on surfaces, 3D models, mathematical art

Domains

graph theory, surface topology, genus formula, hypercube graphs, mathematical art, 3D modeling, visualization, physical construction

Methods

2-cell embeddings, genus embeddings, surface projection, wire-frame modeling

Media

corrugated plastic board, clear packing tape, images

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2024 Conference Proceedings

Hypercube Models via Genus Embeddings

Richard H. Hammack

Dept. of Mathematics, Virginia Commonwealth University Richmond, Virginia, USA; rhammack@vcu.edu

Abstract

I use an established formula for the genus of a hypercube graph to create images and models of $n$ -dimensional hypercubes. These constructions make hypercubes easier to visualize, yield interesting visual images and models, and are the genesis for several of my artworks.

Introduction

This paper concerns the visualization of hypercubes, $n$ -dimensional analogues of the familiar 3-dimensional cube. The approach is to embed hypercube graphs in their surfaces of minimum genus, which can be placed in an ambient 3-dimensional space. This yields 3-dimensional models of hypercubes, with select faces forming an unbroken surface with no self-intersections. One can visually “walk through” such a model, see how the various cells fit together, and thus comprehend the structure of high-dimensional cubes.

I assume you (the reader) have at least a passing acquaintance with graph theory, surface topology and hypercubes, but we will quickly review the relevant ideas in order to synchronize our notations and conventions. The next three sections review 2-cell embeddings of graphs on surfaces, hypercubes, and methods of projecting $n$ -dimensional space to two or three dimensions.

The main idea comes in the final section, which explains how select faces of a hypercube form a surface that the hypercube graph is embedded in. I also showcase two of my artworks that grew from these ideas.

Graphs on Surfaces

Recall that the bounded orientable surfaces are the sphere, the torus, the 2-holed torus, and, in general, tori with $n$ holes. (Non-orientable surfaces are those containing a Möbius band, and they do not play a role in this paper.) The number of holes in a surface is called its genus. We denote the surface of genus $n$ by $T_n$ . If $T$ is an arbitrary surface, we denote its genus by $\gamma (T)$ , so $\gamma (T_n)=n$ . (The sphere has genus 0, and is thus denoted as $T_0$ .) Figure 1 shows some examples. See Chapter 2 of Goodman [3] for background on surfaces.

Figure 1: Examples of Tori. The sphere $T_0$ (left) followed by $T_1$ , $T_2$ and $T_3$ .

Determining the genus of a surface can sometimes take a few moments of thought. Consider the surface on the far left of Figure 2, whose genus may not be immediately apparent. But if we deform it (as if it were made of some malleable material) as indicated, we see that its genus is 5. Now convince yourself that the surface in Figure 9 (right) also has genus 5!

Hammack

Figure 2: Deforming a surface to determine its genus.

A graph is an object consisting of a finite number of vertices (points) together with some number of edges connecting pairs of vertices. The genus of a graph $G$ , denoted $\gamma (G)$ , is the smallest integer $n$ for which $G$ can be drawn on $T_n$ without crossed edges. A drawing of $G$ on a surface, without crossed edges, is called an embedding of $G$ on the surface. An embedding of $G$ on a surface of genus $\gamma (G)$ is called a genus embedding. For example, for the $G$ on the left of Figure 3, $\gamma (G)=0$ , because we can draw $G$ on the surface of a sphere $T_0$ , as shown in Figure 3. The figure also shows embeddings of $G$ on $T_1$ and $T_2$ , but, as $G$ can be embedded in $T_0$ , we have $\gamma (G)=0$ . The embedding of $G$ on $T_0$ is a genus embedding, and the other embeddings in Figure 3 are not genus embeddings. (See [2] for a standard introduction to these topics.)

Figure 3: A graph $G$ (left) and three embeddings of $G$ on surfaces. The first two embeddings are 2-cell embeddings. But the embedding on the far right is not a 2-cell embedding.

A graph embedded on a surface divides the surface into regions. (Imagine cutting along each edge with an X-Acto knife. The surface would be cut into pieces, and each piece is a region.) For example, in Figure 3, the embedding in $T_0$ has four regions, while the embeddings in $T_1$ and $T_2$ each have two regions.

We are especially interested in embeddings for which each region—if flattened—is a polygon. Such embeddings are called 2-cell embeddings. The embedding in $T_0$ in Figure 3 is a 2-cell embedding, as the regions are two triangles and two squares. The embedding of $G$ in $T_1$ in Figure 3 is also a 2-cell embedding, as its two regions are a triangle and an 11-gon. (Seeing the 11-gon may take a moment of visual analysis.) But the embedding of $G$ in $T_2$ is not a 2-cell embedding, because one of the regions is not a polygon at all, but rather a portion of a torus. Given a 2-cell embedding, we call its polygon regions faces. It is a fact that every genus embedding is a 2-cell embedding.

The remarkable Euler genus formula states that if a 2-cell embedding of a graph in a surface $T$ has $\nu$ vertices, $e$ edges and $f$ faces, then

(Theorem 7.1 of [2].) Check this formula on the 2-cell embeddings in Figure 3.

Hypercube Models via Genus Embeddings

Hypercubes

Our primary subjects are the $n$ -dimensional hypercubes $H_n$ , and the hypercube graphs $Q_n$ , described below.

For an integer integer n > 0 , the $n$ -dimensional hypercube graph, denoted $Q_n$ , is the graph whose vertices are the binary strings of length $n$ , and for which an edge joins any two vertices that differ in exactly one position. Figure 4 shows $Q_2,Q_3$ and $Q_4$ . The hypercube graph $Q_n$ is also called the $n$ -cube graph.

Figure 4: The 2-, 3- and 4-dimensional cubes.

Figure 4 highlights the fact that the edges of $Q_n$ can be properly colored by colors $\{1,2,\dots ,n\}$ , where an edge is colored $k$ if its two endpoints differ in position $k$ . Let’s call this the standard coloring of $Q_n$ . Observe that $Q_n$ has $2^n$ vertices (which is the number of $n$ -digit binary strings). Each vertex has degree $n$ (as any vertex is incident with one edge of each color), so the number of edges in $Q_n$ is $\frac{1}{2}n{2}^n=n{2}^{n-1}$ .

It is natural to think of $Q_n$ as a wire-frame model in ${\mathbb{R}}^n$ as follows: Each vertex corresponds to a point in ${\mathbb{R}}^n$ in the obvious way (e.g., 0010 corresponds to $(0,0,1,0)\in {\mathbb{R}}^4$ , etc.), and each edge is a straight line segment connecting vertices that differ in only one coordinate.

Let $I=[0,1]$ be the unit interval in $\mathbb{R}$ . Then $Q_n$ is the 1-skeleton (i.e., the vertices and edges) of the polytope $H_n=I\times I\times \cdots \times I=\{(x_1,x_2,\dots ,x_n)\mid 0\le x_i\le 1\}\subseteq {\mathbb{R}}^n$ . We call $H_n$ the $n$ -dimensional hypercube, or the $n$ -dimensional cube or just the $n$ -cube. (The $n$ -cube graph $Q_n$ is a subspace $Q_n\subseteq H_n$ .)

Let $O=\{0,1\}$ be the boundary of the interval $I$ , so the vertex set of $H_n$ (and $Q_n$ ) is $O\times O\times \cdots \times O$ ( $n$ times). The edges of $H_n$ (and $Q_n$ ) are the components of the products $O\times O\times \cdots \times I\times \cdots \times O$ having only one factor of $I$ . The faces (also called the 2-cells) of $H_n$ are the connected components of the products

that have exactly two factors of $I$ . As there are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ ways to choose the positions for the two factors of $I$ , and 2 possibilities (0 or 1) for each of the remaining $n-2$ coordinates, it follows that $H_n$ has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)2^{n-2}$ faces, and each face is isometric to a square (2-cube) $I\times I$ .

In a similar vein, for any $1\le k\le n$ , the hypercube $H_n$ has $\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{n-k}$ so-called $k$ -cells, each one a copy of $I^k=H_k$ . In particular, the number of $(n-1)$ -cells in $H_n$ is $\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)2^{n-(n-1)}=2n$ . (We also refer to the $(n-1)$ -cells as simply the cells of $H_n$ .) Note that $H_3$ has six cells (its six faces, each an $H_2$ ) and $H_4$ has eight cells, each one a cube $H_3$ . (It is not hard to pick out these eight cells in Figure 4.)

Hammack

Rudiments of Projection

In drawing (or building models of) hypercubes and other $n$ -dimensional figures, we adapt ancient and well-worn canons of representation, and a brief nod to them is appropriate.

In linear projection, an $n$ -dimensional object in ${\mathbb{R}}^n$ is projected to ${\mathbb{R}}^d$ by a linear transformation. (Here $d=2$ for a drawing, or $d=3$ for a sculpture or 3D model.) To set up a linear projection $P:{\mathbb{R}}^n\to {\mathbb{R}}^d$ , begin by selecting $n$ vectors $\{v_1,\dots ,v_n\}\subseteq {\mathbb{R}}^d$ , which are to be the images of the standard basis $\{e_1,\dots ,e_n\}$ of ${\mathbb{R}}^n$ . Then any point $(x_1,\dots ,x_n)$ in ${\mathbb{R}}^n$ projects to $P(x_1,\dots ,x_n)=x_1{v}_1+x_2{v}_2+\cdots +x_n{v}_n\in {\mathbb{R}}^d$ . In linear projection, parallel lines project to parallel lines (or in degenerate cases, to points). See Figure 5 (left).

Figure 5: Projections of the 4-cube. Left: linear projection using ${\nu }_1=(1,0)$ , ${\nu }_2=\frac{\sqrt{2}}{2}(1,1)$ , ${\nu }_3=(0,1)$ , and ${\nu }_4=\frac{\sqrt{5}}{2}(-1,1)$ . Center: perspective projection; Right: informal perspective.

Next consider perspective projection, which is a map $P:{\mathbb{R}}^n\to {\mathbb{R}}^{n-1}$ . This was (for $n=3$ ) a well-developed system by the Renaissance. Here the eye of a viewer is located at a viewpoint $v=(v_1,\dots ,v_n)\in {\mathbb{R}}^n$ , and an $(n-1)$ -dimensional hyperplane $V\subseteq {\mathbb{R}}^n$ is chosen as a picture space. An arbitrary point $x\in {\mathbb{R}}^n$ projects to the point $P(x)\in V$ that is the intersection of the line through $v$ and $x$ with $V$ . In this system, parallel lines in ${\mathbb{R}}^n$ that are not parallel to $V$ project to non-parallel lines in $V$ that meet at a vanishing point (in $V$ ).

For example, taking $\nu =(\frac{1}{2},\frac{1}{2},\frac{1}{2},-1)\in {\mathbb{R}}^4$ and $V=\{(x_1,x_2,x_3,0)\mid x_1,x_2,x_3\in \mathbb{R}\}\subseteq {\mathbb{R}}^4$ , the 4-cube projects to the configuration in Figure 5 (center). The image is a cube with a smaller cube inside it, with corresponding points joined by lines (in blue) that meet at a vanishing point. The smaller cube is further from the viewer than the larger cube, in the direction of the 4th dimension. (The smaller cube is the 4-cube cell whose points have 4th coordinate 1. The larger cube is the cell whose points have 4th coordinate 0.)

Very often we tacitly compose a perspective projection ${\mathbb{R}}^n\to {\mathbb{R}}^{n-1}$ with a linear or perspective projection ${\mathbb{R}}^{n-1}\to {\mathbb{R}}^d$ for $d\in \{2,3\}$ , so that the image is a drawing or a 3D model. For example, in Figure 5 (center) the perspective view of the 4-cube has been composed with a linear projection ${\mathbb{R}}^3\to {\mathbb{R}}^2$ to make it a flat image. We may be barely cognizant of this step, since we are so used to reading 2D images as 3D.

The visual language of perspective is flexible enough that its rules may be bent or broken, with no loss of image viability. For example, the blue edges of the 4-cube in Figure 5 (right) converge to not one but two vanishing points, even though they are parallel in ${\mathbb{R}}^4$ . In fact, careful (or even cavalier) rule-breaking can improve image clarity by avoiding visual clutter and overlap, and the resulting image can even be stronger and more readable than if the perspective were mathematically correct. For the purposes of this paper, let’s say that such an image is rendered in informal perspective. The flexibility afforded by informal perspective will be very convenient, especially in rendering high-dimensional objects, as we will see.

Hypercube Models via Genus Embeddings

Genus Surfaces for Hypercubes

This section introduces a scheme that makes hypercubes easier to visualize. The key idea is that the genus surface for any $Q_n$ (no matter how big $n$ is) can be embedded in our familiar world ${\mathbb{R}}^3$ , and (as we will see) this surface can be built from faces of $H_n$ .

Beineke and Harrary [1] and (earlier, in German) Ringel [6] proved that the genus of the graph $Q_n$ is

(Note that this gives $\gamma (Q_2)=0$ , $\gamma (Q_3)=0$ , $\gamma (Q_4)=1$ , $\gamma (Q_5)=5$ , and $\gamma (Q_6)=17$ , and it should be clear that this is correct at least for $Q_2$ and $Q_3$ , as they can be drawn on the sphere $T_0$ .)

In a more recent paper [4], Paul Kainen and I show that, for any n > 2 , a genus embedding of $Q_n$ can be constructed by selecting a certain subset of $H_n$ ‘s faces that fit together edge-to-edge to form a surface with $Q_n$ automatically embedded in it. The recipe for this is simple. By the standard coloring, each (square) face of $H_n$ is colored by edges of two colors, with opposite edges having the same color. (See Figure 6.) If a face has edge colors $k$ and $\ell$ , we say that it has bicolor $k\ell$ . Let $T$ be the union of all $H_n$ faces with bicolors

Note that if an edge of $Q_n$ has color $k$ , it belongs to exactly two faces in $T$ , with bicolors $(k-1)k$ and $k(k+1)$ . It follows that $T\subseteq {\mathbb{R}}^n$ is a surface in which $Q_n$ is 2-cell embedded, with all faces squares. Furthermore, $T$ is connected because $Q_n$ is connected. (And, as shown in [4], $T$ is orientable.)

Figure 6: A typical square bicolored $k\ell$ . The four vertices differ only in the $k$ th and $\ell$ th coordinates. As there are $2^{n-2}$ ways to fill the $n-2$ unlabeled coordinates, $Q_n$ has $2^{n-2}$ squares with this bicolor.

We claim that $T$ is actually the genus surface for $Q_n$ . To see this, we will calculate the genus of $T$ with Euler’s formula (1), and show that the result agrees with the value of $\gamma (Q_n)$ given by Equation (2). Now, as explained in the caption of Figure 6, for any two colors 1 \leq k < \ell \leq n in the standard coloring of $Q_n$ , there are $2^{n-2}$ squares in $H_n$ that have bicolor $k\ell$ . And because $T$ is made up of the squares of $H_n$ that have one of the $n$ bicolors 12, 23, 34, …, (n-1)n, n1, it follows that $Q_n$ is embedded in $T$ with $n{2}^{n-2}$ faces. And we know that $Q_n$ has $2^n$ vertices and $n{2}^{n-1}$ edges. By Euler’s formula (1),

which is the genus of $Q_n$ , by Equation 2. Consequently, we have embedded $Q_n$ in a surface $T$ of lowest possible genus.

Of course this genus surface $T$ lies in ${\mathbb{R}}^n$ , and all of its faces are squares of unit side-length (and $90^{\circ }$ angles). But any orientable surface can be embedded in ${\mathbb{R}}^3$ . Thus we should be able to build 3-dimensional models of $T$ , perhaps with some of the faces distorted with perspective or informal perspective.

To illustrate, let’s carry out the above construction of $T$ for $Q_3$ , $Q_4$ and $Q_5$ .

Hammack

First, $Q_3$ . Color the edges of $Q_3$ 1 (red), 2 (green) and 3 (blue), as in Figure 4. According to our construction, we form a surface $T$ by including the red-green faces, the green-blue faces, and blue-red faces of $H_3$ . These are in fact all the faces of $H_3$ , and we get the six faces shown in the left of Figure 7. They form the boundary of the 3-cube, which is topologically equivalent to the sphere $T_0$ . So we have an embedding of $Q_3$ in $T_0$ .

Next, consider $Q_4$ , with edges colored red, green, blue and black, as in Figure 4. Our construction dictates that we form a surface $T$ by including the red-green faces, the green-blue faces, the blue-black faces and the black-red faces of $H_4$ . There are 16 such faces. One way of embedding them in ${\mathbb{R}}^3$ is shown on the right of Figure 7. (Some faces are foreshortened with informal perspective to prevent the surface from intersecting itself.) The resulting surface is $T_1$ , the torus, so we have embedded $Q_4$ in $T_1$ . This surface does not include the red-blue and green-black faces of $H_4$ , but we clearly see their perimeters because their edges belong to the included faces. In visually “walking through” the hole of the torus, we walk through all four red-blue faces. And we see the perimeters of all four green-black faces, which are inside the torus. This embedding also makes it easy to pick out all 8 cubic cells (find them!) and to see how they fit together face-to-face. Also note that for any edge, it is easy to pick out the three cubic cells that share that edge.

This model formed the basis for one of the pop-up cards in my 2023 series 4 Views of the 4-Cube, which consists of four pop-up designs that unfold to various projections of the 4-cube. (Each was issued in a limited preliminary run of 22 cards.) Figure 8 shows my Toroidal Hypercube, which opens up to a 3D realization of the toroidal embedding of the 4-cube.

Figure 7: Genus embeddings of $Q_3$ and $Q_4$ .

Figure 8: A pop-up card from my series 4 Views of the 4-Cube, showing the genus embedding of $Q_4$ .

Hypercube Models via Genus Embeddings

Finally, let’s apply our construction to get a genus embedding of $Q_5$ . Recall that $\gamma (Q_5)=5$ . Say the five edge colors of $Q_5$ are 1, 2, 3, 4 and 5. We thus include the 5-cube faces colored 12, 23, 34, 45, and 51 to obtain an embedding of $Q_5$ in $T_5$ . With a combination of intuition and trial-and-error, I created some informal perspective models of this surface, shown in figures 9 and 10.

Figure 9: Two views of the 5-cube. Linear projection (left), and $Q_5$ embedded in its genus surface $T_5$ (right).

Figure 10: Study for 5-Dimensional Box, two views. Laser printed card stock and tape, $4^{\prime \prime }\times 4^{\prime \prime }\times 4^{\prime \prime }$ . In this construction the 5-cube graph is minimally embedded in a surface of genus 5, made from 40 of the 5-cube’s 80 faces.

Figure 10 is a small (4 by 4 by 4 inches) study for a larger work that I plan to undertake. This work, to be entitled 5-Dimensional Box, will be made with translucent corrugated plastic board and clear packing tape.

The genus embeddings in Figure 9 and Figure 10 do not include the 5-cube faces colored 13, 35, 52, 24 and 41. Thus the embeddings use exactly half the 80 faces of the 5-cube. (The other 40 faces would form a surface isometric to the one shown here, as you may care to check.) Thus you can visually “walk through” this model and see all the edges and half the faces of $H_5$, without any intersections. But the missing faces are clearly visible because their perimeters are edges of faces that do belong to the embedding. In walking through the model we can see the perimeters of the faces that are not included on the surface; we walk through some of them, while others are inside the surface.

I believe you will agree that the 5-cube’s structure is much easier to comprehend in the genus embedding models than in more traditional linear projections. To underscore this, compare the two images in Figure 9. You will probably find that the following exercises are much easier if you are examining the genus embedding.

Exercise 1: Locate all 80 faces of $H_5$.

Exercise 2: Identify all ten cells of $H_5$. (The cells are 4-cubes, and each appears in perspective, as in Figure 5, or in informal perspective.)

Exercise 3: The 5-cube has 40 3-cells (each one a 3-cube). Find them (or at least some of them). For each one, find the two 4-cube cells that share it.

Exercise 4: For an arbitrary vertex, find five 4-cube cells that share this vertex.

Exercise 5: For an arbitrary edge, find four 4-cube cells that share this edge.

Although I have yet not made models for genus embeddings of hypercubes of dimension greater than 5, the methods of this paper—or adaptations of them—may produce new and unexpected representations of such objects. In addition to higher-dimensional cubes, we could consider objects such as $n$-dimensional simplexes or octahedra. For example, as proved in [7], the complete graph $K_n$ has genus $\gamma (K_n)=\lceil (n-3)(n-4)/12\rceil$. Since $K_n$ is the 1-skeleton of the $n$-dimensional simplex, we should be able to construct genus embeddings using select (triangular) simplex faces. Similar remarks hold for $n$-octahedra (cross-polytopes) [5].

Acknowledgements

I am heartened by the referees’ constructive comments, and for their obviously careful reading of the paper. I am grateful to be supported by Simons Collaboration Grant for Mathematicians 523748.

References

• [1] L. W. Beineke and F. Harary. “The genus of the $n$-cube.” Canad. J. Math, vol. 17, 1965, pp. 494–496.
• [2] G. Chartrand, L. Lesniak and P. Zhang. Graphs and Digraphs, fifth edition. Chapman & Hall/CRC Press, 2011.
• [3] S. E. Goodman. Beginning Topology. Thompson Brooks/Cole, 2005.
• [4] R. Hammack and P. Kainen. “A new view of hypercube genus.” American Mathematical Monthly, vol. 128, 2021, pp. 352–359.
• [5] M. Jungerman and G. Ringel. “The Genus of the n-Octahedron: Regular Cases.” J. Graph Th. vol. 2, 1978, pp. 69–75.
• [6] G. Ringel. “Über drei kombinatorische Probleme am $d$-dimensionalen Würfel und Würfelgitter.” Abh. Math. Univ. Hamburg, vol. 20, 1955, pp. 10–19.
• [7] G. Ringel and J. W. T. Youngs. “Solution of the Heawood map-coloring problem.” Proc. Nat. Acad. Sci. USA. vol. 60, 1968, pp. 438–445.