Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

1) Relative to one another, how computable are the various knot homology theories? For example, how many crossings can we allow a knot and still hope to compute its Khovanov homology, versus its knot Floer or Khovanov-Rozansky homologies? (The latter two seem to be generally unlisted at the Atlas; KF at least has a page about how it can be computed, but KR seems totally absent. If I'm just not seeing the right link, feel free to let me know)

2) Do the algorithms by which these invariants are computed share common features, or are they really very specific to the particular homology being computed?

For example, people computing KF homology draw square pictures that look very different from the pictures drawn by people doing Khovanov homology. On a less superficial level, KF algorithms (as far as I can tell) appear to be 'global' in an essential way, while Khovanov calculations can be done locally, breaking a knot into smaller pieces and then working with the pieces. So I'm led to believe the computations involved are different in a really fundamental way, but would be interested to see some combinatorial connection (as opposed to a topological relationship). I have no idea how KR homology is computed, so have no idea how closely related the computations involved are to, say, ordinary Khovanov homology.

share|improve this question
    
Hi - though I'm no expert, the paper of Carqueville and Murfet arxiv.org/abs/1108.1081 seems relevant. –  Alexander Moll Nov 16 '11 at 7:24

2 Answers 2

Khovanov homology can be computed quite well, by Dror Bar-Natan's algorithm, as Ben says. It's nowhere near as good as algorithms for computing the Jones polynomial however.

The basic idea is that the speed of the computation depends largely on the "girth" of the link diagram. This is greatest number of intersections you see with a horizontal line. Within each girth, the algorithm applies to be a small degree polynomial in the number of crossings. However changing the girth dramatically affects the algorithm. Girth 14 is critical -- we can do up to about 80 crossings. See my paper with Freedman, Gompf and Walker on the smooth 4-d Poincare conjecture for details. Girth 12 and below is 'easy', and yes, 100 crossings is plausible, but more likely in weeks than seconds! Girth 16 and above seems to be out of range of current computers.

It's important to point out that memory constraints are the real issue for large Khovanov homology calculations. There's only a limited degree to which you can parallelize the computation, and so you end up wanting a single big computer with tonnes of RAM. The latest implementation of Dror's algorithm (my partial rewrite of Jeremy Green's program) tries to cache a lot of stuff of disk, but nevertheless we've done runs on 32gb machines and wished we had more memory!

As Ben says, Khovanov-Rozansky is much harder, and the purely combinatorial calculations you do for Khovanov homology get replaced by lots of commutative algebra. Ben at one point had a program that was doing this -- I'm not sure what the status of that is.

Knot Floer homology is a different matter. Even though there is now a nice 'cube of resolutions' picture for Knot Floer homology, it's only directly for knots, rather than tangles, so Dror's divide and conquer strategy doesn't apply. Dylan Thurston and others have a local description for tangles, but I don't know that anyone has tried implementing it. Computers aren't yet good at A_\infty tensor products!

If anyone is ever interested in writing better programs for Khovanov homology (or indeed trying to generalize to cover some of the other cases), please contact me, as I have some ideas! I'm no longer interested in writing code myself, but I'm happy to talk about it and assist. Particularly next semester at MSRI, if anyone is interested in doing some link homology programming they should talk to me.

share|improve this answer
    
Robert Lipshitz just pointed out to me some errors in what I said above about knot Floer homology. The extension to tangles is due to Zarev arxiv.org/abs/0908.1106, not Dylan et al. There are also perfectly good computer programs by now that do calculations based on $A_\infty$ tensor products, by Adam Levine, Peter O, and Robert. –  Scott Morrison May 6 '11 at 20:38

As far as I know, the only knot homology that can be efficiently computed is Khovanov homology, using Dror Bar-Natan's algorithm. Don't hold me to this, but my understanding is that Dror's program could do 100 crossing knots in seconds, which is lightyears ahead of anything else. Knot Floer homology has a combinatorial description, but it's not very efficient to compute.

As far as I know, no one really knows how to compute Khovanov-Rozansky homology. I can do some computations by hand in HOMFLY homology, but getting a computer to do so seemed to be quite difficult. Some grad student who's good at programming needs to attack the problem.

Very little is known about the connection of KF to other homologies. This is one of the big open problems in the field. Khovanov homology is a special case of Khovanov-Rozansky, though this is not obvious from the original definitions.

share|improve this answer
    
Not quite; 80 crossing knots in days is the outer boundary for that algorithm. –  Scott Morrison Nov 5 '12 at 0:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.