# Linked polytopes and toric grid tessellations

In my recent posting on four-dimensional polytopes containing linked or knotted cycles of edges, I showed pictures of linked cycles in three examples, the (3,3)-duopyramid, hypercube, and (in the comments) truncated 5-cell. All three of these have some much more special properties: the two linked cycles are induced cycles (there are no edges between two non-consecutive vertices in the same cycle), they include all the vertices in the graph, and their intersection with any two- or three-dimensional face of the polytope forms a connected path.

When this happens, we can use it to construct a nice two-dimensional grid representation of the polytope. The set of pairs \( (x,y) \) where \( x \) is a position on one of the cycles (at a vertex or along an edge) and \( y \) is a position on the other cycle form a two-dimensional space, topologically a torus. We can think of this as a grid with wrap-around boundary conditions, where the grid lines correspond to vertex positions on one or the other cycle. The number of grid lines in each dimension is just the length of the cycle. Then, each non-cycle edge of the polytope connects one point from each cycle, so it can be represented as a grid point on this torus. Each two-dimensional face of the polytope has two non-cycle edges, and can be represented as a line segment connecting the corresponding two grid points (perhaps wrapping around from one side of the grid to the other). And when we draw these grid points and line segments, they divide the grid into cells (again, perhaps wrapping around) that turn out to correspond to the 3-dimensional faces of the polytope. So all the features of the polytope that are not part of the two cycles instead show up somewhere on this grid.

For instance below, in this two-dimensional grid representation, are the duopyramid (two 3-cycles, so a 3 × 3 grid), hypercube (8 × 8 grid), and truncated 5-cell (10 × 10 grid) again. I've drawn these with the wraparound points halfway along an edge of each cycle in order to avoid placing a grid line on the boundary of the drawing. In the hypercube and truncated 5-cell, the axes are labeled by numberings of the vertices. For the hypercube, the vertices can be numbered by the 16 hexadecimal digits, where two digits are adjacent if they differ in a single bit in their binary representations. The two eight-vertex cycles can be obtained by cycling through the order of which bit changes. For the truncated 5-cell, the vertices can be numbered by ordered pairs of unequal digits from 1 to 5, where the neighbors of each vertex are obtained by changing the second digit or swapping the two digits.

Another way of thinking about this is that, on the three-dimensional surface of a 4d unit sphere, we can draw two linked unit circles, one in the \( xy \) plane and the other in the \( wz \) plane. The medial axis of these circles (the points on the sphere equally distant from both of them) is a torus, and what we're drawing in this diagram is how a polyhedral version of the same torus slices through the faces of the polytope.

You can read off the structure of each 3-dimensional cell in the polytope from the corresponding polygon in the diagram. Recall that these cells are themselves three-dimensional polyhedra whose vertices have been divided into two induced paths. So (just as in the four-dimensional case) we can make a grid from the product of these two paths, represent non-path edges as grid points, and represent two-dimensional faces as line segments connecting grid points. Each two-dimensional face has two non-path sides, and a number of path sides given by the difference in coordinates between the corresponding two grid points. So, the total number of sides of the face is just two plus the Manhattan length of the line segment representing the face. For instance, the unit line segments in the duopyramid diagram represent triangles, and the squares formed by four of these segments represent tetrahedra (four triangles). The segments of Manhattan length two in the hypercube diagram represent quadrilaterals, and the hexagons formed by six of these segments represent cubes (six quadrilaterals). In order to represent a polyhedron in this way, a grid polygon has to have vertical edges at its left and right extremes, and horizontal edges at its top and bottom extremes, because otherwise a vertex at the end of one of the two paths would have only two incident edges, impossible in a polyhedron. For the same reason each intermediate grid line must have a grid point (representing a non-path edge of the polyhedron) on it. We can make a dictionary of small polyhedra that can be decomposed into two induced paths, and their associated grid polygons:

Notice that the grid polygons don't have to be strictly convex: the octahedron has eight grid points, four of which are at the corners of a 2 × 2 square but the other four of which are in the middle of the edges of this square. But in order for a collection of polyhedra to meet up to form the faces of a four-dimensional polytope, each grid point needs at least three line segments connecting to it (each polytope edge has to be surrounded by three or more two-dimensional faces). This can only happen if each grid polygon has at most one slanted side in each of the four corners of its bounding box. So these polygons are convex except for possibly having vertices on their horizontal and vertical sides. There are also some other constraints on their shape; for instance, a hexagon with two diagonal sides within a 2 × 2 square doesn't correspond to a polyhedron, because it forms a shape that is not 3-vertex-connected.

Given this dictionary, we can form new patterns by tessellating a rectangular wrap-around grid by these grid polygons, and then ask: does the tessellation represent a 4-dimensional polytope? We have to be a little careful here, because we cannot place horizontal or vertical sides that are subdivided (e.g. in the octahedron) next to similar-looking sides that are not subdivided (e.g. in the cube). There are infinitely many possibilities, some of which give known polytopes, and some of which are unknown to me. For instance, extending the grid of squares shown for the (3,3)-duopyramid to grid of squares in a larger rectangle produces the diagram for another kind of duopyramid.

In the drawing below, the left grid tessellation represents a linked-cycle decomposition of the hypersimplex with five tetrahedra and five octahedra (one of the polytopes Gil Kalai asked about in the comments on my previous post). It can be formed from the truncated 5-cell by contracting all of the edges that are not part of tetrahedra; because the cycle edges of the linked cycles of the truncated 5-cell alternate between tetrahedral and non-tetrahedral edges, this contraction preserves the cycle decomposition. The right grid tessellation represents the octahedral prism, with eight triangular-prism cells and two octahedral cells. Therefore, both of these polytopes are linked. In both cases I found the infinite tessellation first, found its smallest period of horizontal and vertical translation, and then was able to identify the corresponding polytope with the help of the low number of cells and high symmetry of these tessellations. But I'm confused by the brick wall in the middle. It has the right number of vertices (10) and the right shape of 3-cells (triangular dipyramids) to be the dual hypersimplex, but the number of bricks is wrong: it should be 10 and is instead 12. (A herringbone pattern of bricks will also tessellate nicely, but then the number of vertices in both cycles would be a multiple of four.) It would be nice to have a theorem characterizing which tessellations give polytopes more generally.

One thing is clear: the polytopes that have linked-cycle decompositions are a very special subclass of the 4-polytopes. For instance, for general 4-polytopes, it remains unknown whether they can have fat face lattices. That is, can a polytope with a small number of vertices and 3-cells have a large number of edges and 2-faces? This can't happen in 3d, by a calculation involving Euler's formula, but the same calculation in 4d doesn't rule out this possibility. But in linked-cycle-decomposable polytopes, the number of cycle edges equals the number of vertices. And because the 3-cells are faces of a torus graph, the number of non-cycle edges (vertices of the torus graph) and 2-faces (edges of the torus graph) are bounded by linear functions of the number of 3-cells. In particular, if there are \( v \) vertices and \( c \) 3-cells, then there can be at most \( v+2c \) edges and at most \( 3c \) 2-cells. This bound is tight whenever the torus diagram is simple (has exactly three edges at each vertex), as it is in the hypercube, truncated 5-cell, and hypersimplex cases.