### Finding knots in graph embeddings

A while ago I wrote a post about indistinguishable sceneries on the Boolean hypercube. The post contained this (pretty, if I may so myself) image:

This is a three dimensional embedding of the four dimensional Boolean hypercube; by “embedding”, I mean putting the vertices and edges of the 4d cube in some way in space, so that the edges do not intersect except at the vertices. In this case, we also colored the vertices, and we did so in such a way so that each vertex has exactly two white neighbors and exactly two black neighbors.

The topic of such colorings is interesting by itself (as I’m sure you all know, for you must have read both the blogpost and the paper on the arXiv, right?), but today I’d like to talk about another peculiar property of this image. If we look at the edges connecting the black vertices with their black neighbors, we get a cycle of length 8. The same thing happens if we look at the edges connecting the white vertices with their white neighbors. Here is the same image, with the two loops emphasized and contrasted for visibility:

The two loops are entwined with each other in what knot theorists call “a non-trivial link”: if you think of them as pieces of elastic string, there is no way to move, rotate, fold, stretch, bend, twist, deform, warp, contort, torture, blackmail, or in any other way convince the two loops to separate, without cutting them. Formally, this link is called the “Hopf Link”, and is often represented in a projection diagram like this:

If I were to summarize the field of knot theory in two words, it would be: “very cool”. In general, it deals with closed loops in (3d) space, and much of it is devoted to discerning between two different knots, or to inspecting what properties are shared between different types of knots. If there is just one knotted loop, it is called a “knot”; if there are two or more loops knotted about each other, they are called a “link”. It is often convenient to portray knots and links in diagrams similar to the ones above; here are a few more examples:

Knot theory is too big a subject for me to properly do it justice in this post, so I’ll just recommend the wonderful and extremely accessible “The Knot Book” by Colin Adams.

Anyway, since I was working with $n$-dimensional hypercubes at the time (we all have that phase), the fact that you can take two cycles of edges in the four-dimensional hypercube and form them into a Hopf link made me wonder:

Question: Is it possible to find any knot or link inside a high-enough dimensional cube?

Admittedly, this is a silly question, and needs some refinement. Knots usually live in 3d space, while the hypercubes are abstract things, or, at best, live in $n$-dimensional space. I need to more precisely define what I mean when I ask “do knots live inside the cube”. So I refined the question:

Question: Given a link $K$, is it always possible to find an embedding of the $n$-dimensional hypercube into 3d space so that some of its cycles form $K$?

Unfortunately, the answer to this question is a trivial yes. For example, this is the two dimensional hypercube, also known as the square:

And here is an embedding of the square which contains the trefoil knot:

Ok, this looks like it’s cheating, right? But in general, embeddings don’t have to have straight lines for edges! We’ll soon talk about what happens when we do force the edges to be straight, but let’s still consider this loopy-lined case. A bit of pondering tells us that in this case, we can form any knot using just a single cycle, of any length! As for links, we only need as many cycles as there are link components. Now, the 2d cube is composed of one cycle of length 4. As the following image shows, the $n$-dimensional cube basically consists of two copies of the $n-1$ dimensional cube, and so each dimension doubles the amount of disjoint cycles:

This means that the $n$-dimensional hypercube contains $2^{n-2}$ disjoint cycles of length 4, and we can definitely find any knot or link for high enough $n$.

Having dealt with this unsatisfying answer, the natural thing to do is to restrict ourselves to straight lines:

Question: Given a link $K$, is it true that for $n$ large enough, it is always possible to find an embedding of the $n$-dimensional hypercube into 3d space where all the edges are straight lines so that some of its cycles form the link $K$?

The answer to this question is also a “yes”, although slightly less trivial than before. For a link $K$, define its “stick number” to be the minimal number of straight sticks required to build the knot. For example, the trefoil knot can be built out of six sticks:

while the Borromean rings can be built out of twelve:

Every knot has a finite stick number, so that every knot can be created by embedding a cycle with a large enough number of edges. For links, we need one such cycle for each component.

How does the hypercube fare in terms of large cycles? Very well, thank you very much. For example, a well known and rather simple theorem states that the $n$-dimensional hypercube always contains a Hamiltonian cycle; that is, there is always a cycle which contains all $2^n$ vertices of the cube (and therefore $2^n$ of the edges). Now, the $n$-dimensional cube consists of $2^{n-k}$ different cubes of dimension $k$, and so contains at $2^{n-k}$ cycles of length $2^k$. So if you have a link with $c$ different components, and the largest stick number of any component is $s$, you just need to take $n$ large enough so that $2^{n- \log s}$ is larger than $c$.

So we have shown the following: For any given link there is $n$ large enough, so that you can always find a way to put the $n$-cube in space with straight edges so that some of its cycles form a given link.
You might want to say that large hypercubes “contain lots of different knots”, but so far we have only shown that it does so in a weak sense. Why “weak”? Because to get the knots, we must choose our embeddings very carefully and with the particular knot in mind.

For example, we know that the embedding of the 4d hypercube shown in the beginning of the post contains the Hopf link. But can we actually find the Hopf link in the 3d cube? The standard embedding doesn’t contain the link (try it out for yourself…):

But if we choose our embedding correctly, we can find one:

The hypercube would “contain lots of knots” in a stronger sense, if, no matter how we choose to embed it, we could always find certain knots and links within the embeddings. This is a much stronger statement about the cube: there is no embedding that “screws up” our knots.

Question: Given a link $K$, is it true that for $n$ large enough, any straight-line embedding of the $n$-dimensional hypercube into 3d space contains the link $K$ in some of its cycles?

It may seem like asking this from the hypercube is asking for too much; hasn’t the poor cube suffered enough? However, results of this type do indeed exist. Here is a very elegant one from Conway and Gordon.

Let $K_n$ be the complete graph on $n$ vertices. Such a graph is usually drawn like this:

Theorem: Every embedding of $K_6$ contains at least one pair of linked triangles.

This theorem was proved in the paper “Knots and Links in Spatial Graphs” by Conway and Gordon (free pdf here), and also appears in The Knot Book. I’ll give just the sketch of it here, and you should fill in the details from Adams’ book.

To every link we can define what is called a “linking number”. This number is calculated as follows. First, choose an orientation along each loop in the link. For example, if we work with the Hopf-link, we might choose:

Now inspect all the crossings in the link. You will find that there are two types of crossings:

For each crossing of the first type, add 1. For each crossing of the second type, subtract 1. Finally, divide the number you got by 2. You have now calculated the link’s linking number! The sign of this number changes depending on the orientation you chose along each loop, but its magnitude is the same no matter which orientation you choose. Additionally, for knots, or loops which aren’t linked together and can be separated, the linking number is always 0.

Note: It takes some work to show that this number doesn’t depend on how you choose to project the link, or that it’s always an integer, but we won’t do that here.

Now take an embedding of $K_6$ which contains a pair of linked triangles; for example, this one:

If you go over all pairs of triangles in this embedding and look at the sum of absolute value of their linking number, you will get a value of 1. As it turns out, there is a way of transforming this embedding into any other possible embedding, so that this sum always keeps its parity. But its parity is odd! So there must be at least one pair of triangles with linking number $\pm 1$. But a linking number of $\pm 1$ implies that the pair of triangles is linked.

So you see, such results are indeed possible, though they require more elaborate arguments. So is every knot strongly contained in some large enough hypercube?

The answer to this question is: I don’t know! (You thought it was yes, didn’t you?).

I do know of a similar result, though. In his paper “Ramsey Theorems for Knots, Links and Spatial Graphs”“, Seiya Negami showed that:

Theorem: Given a link $k$, there is a finite number $R(k)$ such that any linear spatial embedding of the complete graph $K_n$ with $n \geq R(k)$ contains a link equivalent to $k$.

Here “linear embedding” means an embedding where edges are straight lines. The proof is too involved to be brought here.

Now, it’s a nice exercise to show that inside every $n$ dimensional hypercube there sits a refinement of $K_n$. For our purposes, a refinement of a graph is the graph itself, where we can arbitrarily split up the edges into paths of edges instead. For example, here is a refinement of $K_4$:

So if you are willing that some of the “edges” of $K_n$ will actually be a path which may contain several vertices, then you can find a copy of it inside the hypercube.

It’s tempting to say that this is enough for us, and apply the above theorem, but that won’t be true: a straight-edge embedding of the refinement of $K_n$ won’t necessarily be similar to a straight-edge embedding of $K_n$ itself, since the refined edges can be very convoluted, and may give a much more complicated knot than the one you wanted.

Still, I have a hunch that any link is contained in a large enough hypercube. What do you think?