Timeline for Random Reidemeister moves to unknot
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2018 at 12:44 | comment | added | Mark S | Given a grid diagram, call a sequence of translations, castlings, and destabilizations a Dynnikov ratchet. Marc Culler's gridlink (homepages.math.uic.edu/~culler/gridlink) applies a Dynnikov ratchet of 1000 random moves to grid diagrams of grid dimension about 12. I think gridlink is greedy, always taking a destabilization if allowed. Culler suggests that a 12x12 grid may be close to minimal after a Dynnikov ratchet of 1000 moves. | |
| Dec 27, 2017 at 2:51 | history | edited | YCor |
edited tags
|
|
| Nov 23, 2017 at 21:09 | comment | added | Ian Agol | A better question might be whether the expected number of grid moves (exchanges or switches) to untie a grid diagram of the unknot (by "untie", I mean put it in a grid diagram with no crossings). Dynnikov showed that one can untie using switches, and Lackenby showed that one can do it in polynomially many moves. But it's unclear what the expected number of random switches to unknot would be. arxiv.org/abs/1302.0180 | |
| Nov 23, 2017 at 15:53 | answer | added | Mark S | timeline score: 1 | |
| Nov 18, 2017 at 14:49 | comment | added | Mark S | I suspect the answer might change if there were a non-zero "drift" such that the walk along the Reidemeister graph encourages unknotting Type I / Type II moves over "knotting" Type I / Type II? That is, given a knot diagram with a list of potential Reidemeister moves, if one favor unknotting moves that reduce the crossing number over knotting moves that increase the crossing number, then one may have a non-zero probability of unknotting eventually. | |
| May 16, 2017 at 11:36 | history | edited | Joseph O'Rourke |
edited tags
|
|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Oct 24, 2011 at 23:00 | vote | accept | Joseph O'Rourke | ||
| Oct 24, 2011 at 23:00 | answer | added | Joseph O'Rourke | timeline score: 5 | |
| Oct 10, 2011 at 12:55 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 203 characters in body
|
| Oct 10, 2011 at 1:29 | comment | added | Ori Gurel-Gurevich | @Joseph: See my comment to your answer. | |
| Oct 9, 2011 at 17:00 | comment | added | Joseph O'Rourke | @Ori: Thanks for those insights! But now I am puzzled by a theorem in the paper I quoted. Perhaps this just depends on their model, but they prove: "There is a $\lambda > 1$ such that the mean unknotting time of every 2-dimensional SAPT of length $n$ is bounded above by $\lambda^n$." How can this finite upper bound be reconciled with your remarks? | |
| Oct 9, 2011 at 16:42 | comment | added | Ori Gurel-Gurevich | Theo is correct that the diagram space contains lattices of any dimension. Therefore, for any starting diagram of the unknot, there is a positive probability of never unknotting it. (BTW, you can also do it with type I moves). I would just like to add that even if the diagram space was recurrent, the expected number of moves to unknotting would still be infinite, as is the case for simple random walk on any infinite graph. | |
| Oct 9, 2011 at 12:45 | answer | added | Joseph O'Rourke | timeline score: 2 | |
| Oct 9, 2011 at 2:22 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 176 characters in body; added 105 characters in body
|
| Oct 9, 2011 at 2:17 | comment | added | Joseph O'Rourke | @Ryan: Yes, I see now. I was imagining a random knot drawing, and then applying random moves. My fault for not making the relevant distinction! I'm now inclined to Theo's answer: $\infty$! | |
| Oct 9, 2011 at 2:04 | comment | added | Ryan Budney | @Joseph: I think I don't entirely understand your question. There are concrete knot diagrams for which you have to make a large number of Reidemeister moves to simplify them to standard unknot diagrams. So perhaps I've misplaced the quantifier when you use the word "expected" -- are you choosing your knot randomly, as well as choosing the Reidemeister moves randomly? | |
| Oct 9, 2011 at 1:36 | comment | added | Theo Johnson-Freyd | And you do need to allow yourself to increase the crossing number. See e.g. the linked question by Gowers. | |
| Oct 9, 2011 at 1:33 | comment | added | Theo Johnson-Freyd | Here's one reason to think that the answer to your question is $\infty$. Let's work with knots with more than, say, two crossings (as two-crossing knots are not hard to untie). Then there are plenty of strands that with some isotoping can be made parallel. Ok, so among other moves you have access to are the Reidemester-II moves, one direction of which increases the crossing number. If you are not careful, it is easy to use these to include into your diagram space a lattice of large dimension. And you know that it's easy to get lost in them: a drunk bird never arrives home. | |
| Oct 9, 2011 at 1:22 | comment | added | Joseph O'Rourke | @Ryan: Perhaps the cases that require an exponential number of moves are rare? You say, "in general." That is what I would like quantified. And, Yes, it is highly unlikely to wander into the unknot. But has this been proved? Perhaps it follows from Hass-Lagarias in a way I am not seeing... | |
| Oct 9, 2011 at 1:12 | comment | added | Ryan Budney | I'm a little confused as to why you say "surely" as it's does take an exponential number of moves in general. Moreover, I would guess that if you only make random moves, it's highly unlikely you will ever find a route to the unknot -- it seems more likely that you would be endlessly lost in diagram space. | |
| Oct 9, 2011 at 0:54 | history | asked | Joseph O'Rourke | CC BY-SA 3.0 |