Intrinsically knotted graphs on 21 edges

I was skimming through http://www.arxiv.org the other day and found this paper by a student named Barsotti and a professor named Mattman.  Barsotti is/was an undergraduate at CSU Chico and this is his honors thesis, while Mattman is a professor at CSU Chico.  Weirdly enough it looks like Mattman also directed the undergraduate theses of two of my colleagues, Arielle Leitner from UCSB  (wow, nice website!  way better than mine) and Ryan Ottman.  Small world.

So let’s talk a little bit about this paper, shall we?  I gave a half hour talk on it in our little seminar on Tuesday.  Graph theory is one of those fields that is ridiculously  useful.  Computer scientists and anyone who plays with data loves graph theory.  Knot theory is also surprisingly useful since math biology is blowing up right now with knotting of DNA and molecules and such.  This paper lies in the intersection of graph theory and knot theory.

Graph theory.  From my last math post you know what a graph is: a collection of vertices with some edges connecting them.  We’ll be talking about a certain operation you can do to graphs, taking a minor.  A minor of a graph is a graph that you derive from your original graph.  There are three different ways to find minors of a graph: 1) delete a vertex and all the edges connected to it, 2) delete an edge, 3) contract an edge.  The picture shows examples of all three of these.  For number 3, you delete an edge, and you put the two vertices at the end of it together.  Note that the new vertex has 4 edges attached to it, or has degree 4, while the original two each had degree 3.

The big one is ok, but the other three are jail bait.

So there’s this big old theorem from Robertson and Seymour, called the Graph Minor Theorem, which says a couple of things.  For one, if you have infinitely many graphs, you’re definitely holding one that is a minor of another in your hand.  Another way to think of the theorem is if you have a collection of graphs which is closed under minors (e.g. for any graph in your collection, all of the minors of it are in there), you can define this collection by a finite set of forbidden minors.  

A quick example is the collection of all trees (graphs with no cycles or loops in them).  In our picture, 1 and 2 are both trees, while the original graph and 3 both have a loop and so aren’t a tree.  Trees are closed under minors, since taking a minor of a tree will never make a new loop.  Then the theorem says there is a finite set  of graphs which cannot be minors of any tree, and that the set of trees is characterized by not having these as minors.  So to be a tree, it’s necessary and sufficient, as mathematicians like to say, that you have no forbidden minor as a minor.  In the case of trees, the minor is this:

Lady C… er no I meant Sir Cle

This is a loop with a single vertex on it.  If you’re a graph that’s not a tree, you can do a finite sequence of taking minors (e.g. contract the edges in a cycle) until you end up with a single vertex with a loop.  If you are a tree, you can never do this.  Robertson and Seymour’s graph minor theorem took 20 papers to prove.  It’s pretty insane.  But this is how you use it!

So a fun thing that undergraduates and professors do is try to take a family closed under minors and find the finite forbidden minor set.  In the case of a tree, there’s a single forbidden minor.  To talk about other graphs and forbidden minors, let’s switch gears for a moment and go to knot theory.

Trefoil! Versus treplasticwrap. That was a way worse name

Knot theory.  A knot is an embedding of the circle in some crazy way in some crazy place.  Right now we’ll just talk about knots embedded in three space (the world we live in, ).  Embedding is a technical word, but just think of it as putting something somewhere.  In fact, think of a knot as a piece of string, lying one end on the ground, throwing the other end all over itself (looping in and out) and then gluing the two ends together.  Or put in a bunch of ropes, so long as you glue all the ends together to make one continuous loop.

Not a knot… not yet

In this picture, we’d have to glue a gray end and a green end together, and do the same with the other pair, to have an actual knot.  Or you could glue the green ends together and the grey ends together, in which case you would have two knots linked together.

Lots of knots secretly look very simple, like a circle:

Even crazy complicated ones.  Look at this diagram to see what I mean about ‘secretly looking like’:

This diagram is from a paper by Henrich and Kauffman from 2010 (disclaimer: Kauffman is at my school).  [I don’t know why I put in that disclaimer.]

But the trefoil, above, for example, doesn’t secretly look like a circle.  No matter how you pull and prod the strands around, you can’t get a plain old circle again.

This brings us back to graph theory.  A graph is intrinsically knotted if, no matter how you draw it in , you end up with a not-boring knot.  This paper I just read lists all the intrinsically knotted graphs with 21 edges (as you’d expect from the title).  The proof uses some results from Robertson and Seymour’s graph minor theorem.  For instance, it uses the fact that all non-planar graphs are characterized by two forbidden minors- this is Kuratowski’s theorem and I’ll do another post on it sometime.  The proof uses a lot of cool little tricks, but this is just an intro post so I’ll save those for another time.

In case you were wondering, there are 14 intrinsically knotted graphs with 21 edges.  That’s the takeaway!

Tags: graph, graph minor theorem, knot theory, Kuratowski's theorem