# Is there a “knot theory” for graphs?

I think knot theory has been studied for quite a while (like a century or so), so I'm just wondering whether there is a "knot theory" for graphs, i.e. the study of (topological properties of) embeddings of graphs into R^3 or S^3.

If yes, can anyone show me any reference?

If the answer is basically no, then why? Is it just too hard, uninteresting, or can it be essentially reduced to the study of knots (and links)?

## 8 Answers

The theory of knotted trees is obviously trivial. So given a knotted graph $\Gamma$, take a maximal tree in it and you can bring it to a standard form, say to be embedded as a planar object inside a tiny disk that is disjoint from the rest of the knotted graph; which is just the finitely many arcs that make the complement of the tree. But now you can draw $\Gamma$ in the plane so that "everything interesting" (namely, the complement of the tree) is outside of a small disk. Do inversion, and you have a fixed tree outside the disk and a tangle inside it. (Some details depend on whether your vertices are rigid or not, or "thickened" or not, but the conclusion is always more or less the same).

This correspondence between knotted graphs and tangles is not canonical - it depends on the (combinatorial) choice of a maximal tree, and modifying that choice modifies the resulting tangle (in simple ways that will not be stated here).

So topologically speaking, "knotted graphs" are not interesting. They are merely tangles, along with a bit of further combinatorial data (mostly the tree). If you totally understand the theory of tangles (modulo some simple to state actions, which also depend on what rigidity assumptions are made for the vertices), you'd totally understand knotted graphs.

Yet there's lot's of beautiful information in the interaction between the combinatorics of the graph and the topology of the tangle. For example, see my recent paper with Zsuzsanna Dancso, arXiv:1103.1896, in which we study the relationship between knotted trivalent graphs and Drinfel'd associators.

Yes, there are many such results. Conway-Gordon, Sachs in the 80s proved that any map $K_6 \to R^3$ contains two disjoint linked traingles. Robertson-Seymour-Thomas proved found the family of minors that characterizes such property. Lovasz-Schrijver proved that this is equivalent to having Colin de Verderie invariant larger than 4 and the projection on the null space of the Colin de Verderie matrix is a linkless embedding (in the case the null space is of dimension four or less, I forget if this is a theorem or a conjecture?)

There are many papers saying things like, for your favorite Link invariant there is a numnber $n$, such that for any embedding $K_n \to R^3$ one can find a link with nontrivial your favorite invariant. I don't remember the references now, maybe google "ramsey theory for links" or something like that. ($K_n$ is the complete graph on $n$ vertices).

From a more geometrical point of view, here are two things you can do:

One is to look at metric properties. For this look up Kolmogorov-Borodin and the recent paper by Guth and Gromov. Actually expanders were discovered for this reason.

The alternative is to think about the linear structure, namely you can ask whether there are affine subspaces of the ambient space intersecting many of the edges for any embedding. In a recent joint paper with Boris Bukh we called this "space crossings". Because if the affine flat that intersects your edges is of dimension 0 this is precisely a crossing. We investigated the "space crossing numbers" of graphs in $R^3$, but our techniques generalize to graphs in $R^d$. The first result in this direction was Zivaljevic's who proved that $K_{6,6} \to R^3$ has non zero space crossing number. Our main result is an analogue of the classical crossing number inequality which almost implies it.

• I'm leaving this as a comment rather than an answer because it's really the same as what Alfredo already said, but for more of what he mentions in his first paragraph, at a nontechnical level, see en.wikipedia.org/wiki/Linkless_embedding – David Eppstein Oct 30 '11 at 2:55
• "in all the previous results is very important that you are dealing with codimension two". The Conway-Gordon/Sachs result has NOTHING to do with codimension two: any map of the $n$-skeleton of the $(2n+3)$-simplex in $\Bbb R^{2n+1}$ contains a pair of disjoint linked boundaries of the $(n+1)$-simplex (Lovasz-Schrijver, ams.org/journals/proc/1998-126-05/S0002-9939-98-04244-0 and Taniyama, pjm.berkeley.edu/pjm/2000/194-2/p14.xhtml; a third proof is in Example 4.7 in arxiv.org/abs/math/0612082 and a fourth in Example 4.9 in arxiv.org/abs/1103.5457v2). – Sergey Melikhov Oct 30 '11 at 18:30
• "... as a famous result of Zeeman says". The fact that every graph unknots in $\Bbb R^n$ for $n>3$ is trivial (use general position) and has nothing to do with Zeeman. Zeeman's result is about piecewise-linear unknotting of spheres in codimension $\ge 3$. But spheres easily link, and connected manifolds easily knot in high codimensions. In fact, "your favorite" link invariant used in "Ramsey link" theory (and I've seen papers dealing with the Sato-Levine invariant and Milnor's triple invariant) probably has a higher-dimensional extension (certainly in those two cases). – Sergey Melikhov Oct 30 '11 at 19:09
• (con't) In more detail, higher-dim extensions of Milnor's triple invariant detect a Brunnian "Borromean rings" link of three $S^{2k−1}$'s in $\Bbb R^{3k}$, and a higher-dim counterpart of the Sato-Levine invariant (not the original higher-dim Sato-Levine invariant) detects a "Whitehead link" of two $S^{2k−1}$'s in $\Bbb R^{3k}$, $k\ne 3,7$, which has zero linking number. – Sergey Melikhov Oct 30 '11 at 19:20
• Sorry for getting a bit too emotional over the codimension. – Sergey Melikhov Oct 31 '11 at 20:24

Yes, there's plenty of work on this. First of all, you have to define the notion of equivalence that you are interested in. Usually people only care about the graph up to handle-slide (turning the subject into the subject of knotted handlebodies), so you can assume the graph is tri-valent. But you could go further to study graphs up to isotopy and there's work on that too. Much of the technology to study knots translates to studying knotted graphs. Some references:

http://katlas.org/drorbn/index.php?title=The_Alexander_Polynomial_of_a_Knotted_Trivalent_Graph

http://katlas.org/drorbn/index.php?title=The_Kontsevich_Integral_for_Knotted_Trivalent_Graphs

http://ldtopology.wordpress.com/2009/10/29/which-knotted-objects-are-worthy-of-study/

http://www.ms.unimelb.edu.au/~snap/

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.em/1276784791

The last two references are rather nice as they show that much the same way hyperbolic geometry "dominates" traditional knot theory, it plays a similar role in the study of knotted trivalent graphs. In this case orbifolds play a more prominent role.

• The first katlas link looks puzzling. Is there any paper about this Reidemeister torsion of graph complement? I remember finding Viro's Alexander polynomial/Conway function of trivalent graphs (arxiv.org/abs/math/0204290, mi.mathnet.ru/eng/aa74) to be quite enlightening (e.g. in trying to understand the ordinary multivariable Alexander polynomial). But is it related to the Reidemeister torsion? For links, the relation is made very clear in arxiv.org/abs/math/9806035, but this doesn't work for graphs, does it? – Sergey Melikhov Oct 31 '11 at 20:22

whether there is a "knot theory" for graphs...

or can it be essentially reduced to the study of knots (and links)?

As Dror Bar-Natan points out in his interesting answer, it can, "if you totally understand the theory of tangles". If you don't, but you're very generous as to what amounts to a reduction, then it "almost can" (up to about one integer invariant) by a theorem of Roberston, Seymour and Thomas: two knotless, linkless embeddings $f,g$ of a graph $G$ in $\Bbb R^3$ are equivalent (by an isotopy of $\Bbb R^3$) if and only if the restictions of $f$ and $g$ to every subgraph of $G$, homeomorphic to $K_5$ or $K_{3,3}$ are equivalent. Here "knotless" means that every cycle (a subgraph homeomorphic to $S^1$) in $G$ is unknotted, and "linkless" means that every two disjoint subgraphs are separated by an embedded $2$-sphere. To be precise, Robertson, Seymour and Thomas had a slightly different formulation (with "panelled" in place of "knotless and linkless") and the above version is proved in http://arxiv.org/abs/math/0612082.

What is the "about one integer invariant"? As Ryan Budney points out in his interesting answer, it helps to study graphs up to weaker equivalence relation than ambient equivalence or non-ambient isotopy (which, incidentally, already kills all local knots). Taniyama (Topol. Appl. 65 (1995), 205-228) has shown that two embeddings of a graph $G$ in $\Bbb R^3$ are "homologous" (=cobound an embedded $G\times I$+(handles) in $\Bbb R^3\times I$, where each handle is a torus attached by a tube to a $2$-cell, (edge)$\times I$) if and only if they have the same Wu invariant (this integer invariant is really just the $1$-parameter version of the van Kampen obstruction). On the other hand, Shinjo and Taniyama (Topol. Appl. 134 (2003), 53-67) have shown that the vanishing of the Wu invariant of a graph is determined by the vanishing of its restriction to subgraphs homeomorphic to $K_5$, $K_{3,3}$ and $S^1\sqcup S^1$.

Another interesting relation on embedded graphs in link homotopy, i.e. arbitrary self-intersections of connected components are allowed, but distinct components may not intersect. The link homotopy classification of embeddings in $\Bbb R^3$ of a disjoint union of two $S^1$'s and a wedge of $S^1$ is already pretty nontrivial.

• Just to add some hearsay, yet research-related hearsay: I recently heard it claimed that is is an open problem as of today what smallest $c\in\mathbb{N}$ makes the (non-first-order) sentence 'Every knotless abstract finite undirected simple graph $G$ is $c$-colorable.' true. It seems known for half a century that $c\leq 8$. Moreover, it seems to be known, too, that $c>5$. Yet it seems an open problem whether the statement is true with $c=6$. Again, I am reporting hearsay here, and did not stop to search for this particular problem in the literature. And whether this is "theory" is debatable. – Peter Heinig Aug 21 '17 at 17:38

In principle, there is an algorithm to tell if two graphs in $\mathbb{R}^3$ are isotopic, using Waldhausen's method of recognizing Haken 3-manifolds. The complement of a graph (obtained by removing an open regular neighborhood) has a natural pared manifold structure (also keeping track of meridians and longitudes on closed loop components). The pared manifold just means you have a collection of annuli in the boundary, and these annuli come from the regular neighborhoods of the edges of the graph. Waldhausen's theorem may be extended to determine the homeomorphism problem for pared manifolds - although it is not explicitly stated in this form, his method makes use of a more general concept of manifolds with boundary pattern, of which pared manifolds are a special case. It's not hard to see that two graphs are isotopic if and only if their corresponding pared manifolds are equivalent. However, this algorithm has not been fully implemented by computer.

One practical method is to use the program Orb. This allows you to input a graph using a mouse, similar to Snappea/SnapPy. If the graph complement is hyperbolic (in an appropriate sense, where the pared locus corresponds to rank one cusps, and the complementary regions corresponding to vertices of the graph are totally geodesic), then Orb will allow you to tell if two graph complements are isotopic (if it doesn't crash!). There is a relative JSJ decomposition, which allows one to break up a pared manifold into hyperbolic and Seifert pieces (such as the graph generalization of connect sum), but this has not been implemented as far as I know.

The theory of (un)knotted graphs also contributes to knot theory. For example, the theory of tunnel number one knots can be thought of as the theory of embedded theta graphs with a distinguished edge (the tunnel). The operation of band summing two knots (or more generally any rational tangle replacement) can be studied by examining an eyeglasses graph with the separating edge the core of the band. There is a relatively nice interplay between such graphs and other 3-manifold theories like thin position and sutured manifold theory.

It is somewhat surprising (to me) that what to me seems the simplest nontrivial example of theorems exactly fitting the question in the OP has not yet been mentioned in this thread: the embeddings of the Möbius ladders, which are finite simple undirected graphs, into $\mathbb{R}^3$.

This is an answer to

whether there is a "knot theory" for graphs, i.e. the study of (topological properties of) embeddings of graphs into R^3 or S^3. If yes, can anyone show me any reference?

at least in the sense that in the very interesting article Erica Flapan: The Symmetries of the Möbius Ladder. Math. Ann. 283, 271-283 (1989), which I think, could be given a fruitful revival from a point of view of constructive mathematics (e.g., how much of Flapan's proofs/theorems can be done constructively?), the following was done, inter alia (there is more in Flapan's paper):

• in Section 1 of loc. cit. a proof is given that there exists a graph $G$ and an automorphism $\alpha$ of $G$ as an abstract graph, such that there does not exist any embedding of (the geometric realization $\lvert G\rvert$ of ) $G$ into $\mathbb{R}^3$ such that $\alpha$ could be realized by an element of the group of leaving-$\lvert G\rvert$-invariant-as-a-point-set diffeomorphisms of $\mathbb{R}^3$. Note that in this rendition I rendered the author's "group of homeomorphisms of $G$ up to isotopy" into what to me evidently seems equivalent and clearer "automorphism of $G$ as an abstract graph". The example graph used by the author is $G:=$complete graph with six vertices.

• in Section 2 of loc. cit., first a proof in classical logic is given that for any embedding $\eta\colon M_r\to S^3$ of the $r$-rung Möbius ladder $M_r$ into the $3$-sphere $\mathbb{S}^3$, any orientation-reversing diffeomorphism $\varphi\colon S^3\to S^3$ has the property that if it fixes1 $\mathrm{im}(\eta)$ as a pointset, then $\varphi$ does not fix at least $r-2$ of the $r$ rungs of $M_r$. This is, partly, an interesting counterfactural (since the author later gives a proof that for an odd number of rungs, such $\varphi$ are impossible): roughly, if there is a symmetry of the Euclidean-space-embedded Möbius ladder, then it must needs jumble almost all the ladder's rungs. This implication is then put to use to give a proof that for an odd number of $r$ungs, such a $\varphi$ is impossible. Roughly: you cannot reverse the orientation of an embedded odd-rung-number Möbius ladder graph by a Euclidean symmetry. The author then gives an example that for even number of rungs, such isometries do exist. I perceived this to be a result which is very relevant to the OP; it in particular is an interaction between a combinatorial property of the abstract graph (number of rungs) and a concept studied in knot theory: slightly vaguely, one could say: Flapan gave a proof that for rung-numbers $\geq 4$, each odd-rung Möbius ladder is non-amphichiral, while each even-rung Möbius ladder is amphichiral. The smallest example of the latter ladders is the embedding represented by the illustration on p. 272 of loc. cit., when thought of to have precisely four rungs, about which loc. cit. says that it is amphichiral, while if the picture is thought of to represent a Möbius ladder with five rungs, then loc. cit. says that there does not exist any orientation-reversing self-diffeomorphismof $\mathbb{R}^3$ which would fix it as a point set.

(The latter is a precise and usual statement of the matter. A more vague alternative statement one often encountered is 'It is not equivalent to its mirror-image.' wherein 'mirror-image' is either left undefined, or is defined via orientation-reversing self-homeomorphism of $\mathbb{R}^3$, whereupon the alternative statement becomes at least not simpler.)

The amphichirality of the even-rung Möbius ladders is easy to see, the substance of Flapan's results is non-amphichirality of the odd-rung Möbius ladders with at least 5 rungs.

The author on p. 272 of loc. cit. writes

The property of topological achirality for graphs is analogous to the property of amphicheirality for knots.

• in Section 3 of loc. cit., the focus shifts from (non-)existence of orientation-reversing Euclidean symmetries of embedded Möbius ladders, to properties of orientation-preserving such symmetries. The emphasis is on a difference between embeddings into $\mathbb{R}^3$ and embeddings into $S^3$.

This difference is illustrated by the author using the following illustration on p. 278 of loc. cit. which is a an example of what the OP is asking for: this meant to represent a non-knot embedded into $S^3$, namely the abstract undirected simple graph $M_3$, the three-rung Möbius ladder.

Furthermore, one should mention that there is a very recent preprint

Erica Flapan, Thomas Mattman, Blake Mellor, Ramin Naimi, Ryo Nikkuni: Recent Developments in Spatial Graph Theory. arXiv:1602.08122v2 [math.GT]

which is relevant to the OP. Therein, more results on embedded Möbius ladders are summarized, in particular the new paper (published after the OP)

E. Flapan and E. Davie Lawrence, Topological symmetry groups of Möbius ladders, J. Knot Theory Ramifications, vol. 23, no. 14, (2014)

Remarks.

1 Note that in loc. cit. there is a slightly stronger hypothesis than mere fixing the image of the embedding in its entirety. This hypothesis is essential in the special case $r=3$, yet can be left out for all $r\geq 4$, as loc. cit. itself points out on p. 272.

2 The rung-number $r=3$ is an exceptional case. The $3$-rung Möbius ladder is isomorphic to the complete graph $K^{3,3}$, and its geometric realization in $\mathbb{R}^3$ happens to be amphichiral: it is evident that the geometric graph $G$ represented by the illustration in loc. cit. is isotopic to its 'mirror-image'.

Just as Ryan Budney pointed out, instead of ambient isotopy one may consider a weaker equivalence relation on spatial graphs, namely the one generated by isotopy and IH-moves (also known as Whitehead moves). With this definition of equivalence, two knotted graphs are equivalent if and only if they admit isotopic regular neighbourhoods. This equivalence relation has been already considered, for example, by Kinoshita in 1958, and it was named ''neighbourhood equivalence'' for obvious reasons.

Of course, the study of graphs up to neighbourhood equivalence reduces to the study of knotted handlebodies. There exist several invariants of knotted handlebodies. Among them, I have recently become interested in the quandle coloring invariants defined by Ishii in his paper

Moves and invariants for knotted handlebodies Algebraic & Geometric Topology 8 (2008) 1403–1418

In a joint paper with R. Benedetti

"Levels of knotting of spatial handlebodies" http://arxiv.org/abs/1101.2151

we have exploited (among other things, like the Alexander invariants of the complement) these quandle coloring invariants in order to distinguish different levels of knotting for handlebodies.

Just as in the case of knot theory, a good invariant for a knotted handlebody is its complement. However, while Gordon-Luecke's Theorem ensures that a knot is determined by its complement, there exist inequivalent handlebodies whose complements are homeomorphic (this is one of the reasons why I would compare the theory of knotted handlebodies of genus g with the theory of links with g components, rather than with knot theory). On the other hand, Kent and Souto exhibited here

http://arxiv.org/abs/0904.2332

a spatial handlebody whose complement admits a unique embedding in the 3-sphere up to isotopy. Also observe that, due to Fox's reimbedding Theorem, every compact submanifold of the 3-sphere admits a reimbedding as the complement of a finite union of handlebodies in the 3-sphere itself. Therefore, a complete understanding of knotted handlebodies should provide an understanding of spatial domains in general.