Is there a “knot theory” for graphs?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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)?

-

check out: ams.org/mathscinet-getitem?mr=1781912 – Agol Oct 30 2011 at 2:26
You might be interested in the last part of my answer to this question : mathoverflow.net/questions/39650/… – Andy Putman Oct 30 2011 at 2:40

7 Answers

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.

-

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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.

-

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.

-

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.

-

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.

-

1
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 2011 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/… 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 2011 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 2011 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 2011 at 19:20
Finally, the Robertson-Seymour-Thomas result about minors is likely to have an analogue for linkless embeddings of $n$-dimensional simplicial complexes in $\Bbb R^{2n+1}$, $n\ne 2$ (see arxiv.org/abs/1103.5457v2), but I'd skeptical about lower codimension, especially codimension two ($K^n$ in $\Bbb R^{n+2}$ for $n>1$) In fact, I haven't seen any results whatsoever on "codimension two Ramsey theory" ($K^n$ in $\Bbb R^{n+2}$) except for the classical case ($n=1$). – Sergey Melikhov Oct 30 2011 at 19:27
show 2 more comments

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 2011 at 20:22
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 57, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9227115511894226, "perplexity_flag": "middle"}