Arf! Or, What’s with the Title?

Well, I’m glad you asked!

The title of this blog comes from a mathematics research project I did in summer 2006, with one of the professors at Union. The study of intrinsically knotted and linked graphs is a small field combining knot theory and graph theory, which poses the question, “For what kinds of graphs can we claim that every spatial embedding contains at least one knotted cycle/collection of linked cycles?”

A bit of background:

A graph is a set of vertices, pairs of which may or may not be connected by edges. We usually represent a graph by drawing its vertices as points and its edges as lines or curves connecting one vertex to another. It’s important to note that, as far as a graph is concerned, it doesn’t matter where you draw the points and curves–as long as the vertices that should be connected (adjacent) are connected, and the ones that shouldn’t be are not, then it’s the same graph. This is a diagram of a graph with five vertices, with one of its edges identified by the coordinate pair containing its two vertices.

We can embed the graph in 3-space by choosing a particular point for each vertex, and a particular curve for each edge, beginning and ending at the appropriate points. (No two edges may intersect except at a shared vertex, and no edge may cross a vertex other than its endpoints, but that oughta be obvious.) A particular choice of points for vertices and curves for edges is called a (spatial) embedding of the graph, and now location does matter; these two embeddings of the same graph are not the same:

Note that in both drawings when one edge crosses above or below another (or itself), we make a break in the one below to indicate that they’re not actually intersecting, which would be a no-no.

Taking a break from graphs, let’s talk about knots. A mathematical knot is a lot like a knot you’d tie in your shoelace, except for one important thing–the ends are joined. (Otherwise they would be boring; you could always untie them.) Specifically, a knot is a simple closed loop in 3-space. The simplest possible knot is just a circle, or anything that can be untwisted without breaking the strand to form a circle–we call this the trivial knot.

The next simplest knot is the trefoil knot–the ordinary overhand knot, with ends joined. From here on out the knots get more and more complicated, and the number of times a knot diagram crosses itself goes higher and higher. For these purposes, though, we’re only interested in the trivial and trefoil knots.

Alright, so how do we combine knots with graphs? Well, a cycle in a graph is a sequence of edges that form a closed loop in the graph. Here are a couple examples:

The blue cycle on the right is a special one–it passes through all five vertices of the graph. A cycle that passes through all vertices of a graph is called a Hamiltonian cycle.

You can see where this is going–look at one of the cycles in a particular spatial embedding of a graph. That’s a knot! True, it might only be the trivial knot, but if the edges are wild enough or if there are enough of them, the cycle might be a non-trivial knot, like the trefoil.

Here’s where it gets fun:

In 1983 John Conway and Cameron Gordon started this entire unholy fusion of knot theory and graph theory, when they published a paper proving that K7, the complete graph on 7 vertices (I’ll explain that in a minute), is intrinsically knotted: every possible embedding has at least one knotted (non-trivial) Hamiltonian cycle.

The complete graph on n vertices, denoted Kn, is the graph with exactly n vertices such that each pair of vertices is connected by one edge. Here are a few examples:

Note that it’s not hard to produce one embedding of a graph with a knotted Hamiltonian cycle. Here’s an example with K7. The hard part is to show that it’s impossible NOT to have a knotted Hamiltonian cycle.

So how did Conway and Gordon do it? (I won’t give the full proof here, just the idea.) An important tool from knot theory (which is a branch of topology) is the knot invariant–any property of a knot whose value is the same no matter how the knot is arranged in space. For our purposes, the invariant we’re interested in is the Arf invariant (named after Cahit Arf), which takes on the value 0 or 1 for each knot. The value of the Arf invariant for a knot k is denoted α(k). In particular, α(trivial knot)=0 and α(trefoil)=1.

So what we’ll do is find the Arf invariant for every single Hamiltonian cycle in an embedding of K7, and take their sum mod 2 (that is, divide the sum by 2 and then look at the remainder, which will be 0 or 1). For each embedding, call this sum σ.

The Arf invariant is special because the way to determine it involves looking at the places where the knot crosses over itself, and specifically what happens when you change an overcrossing to an undercrossing. So, since any graph embedding can be changed into any other graph embedding by swapping certain edge crossings (and changing the way the edges are curved, but we don’t need to worry about that), we can get a handle on how σ, the sum of the arf invariants mod 2, changes from one embedding to the next.

It turns out that in the case of K7, σ doesn’t change at all. Its value is the same for every embedding of K7. So now the only question is, what is its value? If σ = 1, we’ll know that there are always an odd number of Hamiltonian cycles with Arf invariant 1. But “an odd number” means at least one, and that means at least one non-trivial cycle! (Remember, α(trivial knot)=0.) On the other hand, if σ = 0, all we’ll know is that an even number of Hamiltonian cycles have Arf invariant 1, and that could be twenty, two, or zero.

We need more information–if we could find out the value of σ for just one embedding of K7, we’d have our answer. Conway and Gordon provided the following embedding of K7, which (they claim) has exactly one knotted cycle, a trefoil knot, while all the remaining cycles are trivial.

I can’t find the knotted cycle. Can you? Let’s give them the benefit of the doubt. (I’m lazy and I’m not going to check all 7!/(7*2)=360 cycles.)

So this embedding of K7 has σ = 1, which means every embedding does, which means… K7 is intrinsically knotted!

Strictly speaking, a graph is intrinsically knotted if every embedding has some knotted cycle, not necessarily a Hamiltonian cycle. So right away we know that K8, K9, K10, … are intrinsically knotted. (Why?) We can ask stronger questions, though, and that was what my research project was about. We wanted to prove that every complete graph on n vertices, with n ≥ 7, is guaranteed to have a knotted Hamiltonian cycle in every embedding. This is one of those questions that you just KNOW has an obvious answer, but it turned out to be–forgive me–a knotty problem. Finally by the end of the allotted time, we were able to extend Conway-Gordon’s result in several ways, including showing that K8 has the property, but our method failed for larger complete graphs.

Nevertheless, I’m proud of the work I did on this problem, and last April when I attended the Hudson River Undergraduate Mathematics Conference (HRUMC’07) I gave a 15-minute talk on my research (some of this discussion is lifted straight from that presentation). However, before the conference I learned that Joel Foisy, one of the few mathematicians publishing in this field, would be attending the conference. When I went and looked him up, what did I find under Recent Publications? “Knotted Hamiltonian cycles in spatial embeddings of complete graphs.” He and his four REU students had been working on this same problem that summer, and they had actually solved the full problem!

Anyway, their proof was a very elegant one and I incorporated a sketch of it into my talk at the conference, which Dr. Foisy attended, and he complimented me on my version of the proof later. Another professor who had attended told me it was “a real mathematician’s talk”, which felt great!

And now, since you’ve made it this far, it’s only fair to reward you with the limerick I wrote to end my talk at HRUMC:

The study of knotting in graphs

Is always good for some laughs:

The Arf you’ll applaud,

‘Cause the sum of it’s odd

Over all closed Hamiltonian paths.

________________________________________

[1] J. Conway, C. McA Gordon, Knots and links in spatial graphs, J. of Graph Theory 7 (1983), 445-453.