Snake mistake!
May. 9th, 2019 03:43 pmSo I emailed the authors of that Snake paper, and in the resulting discussion it turns out I made a serious mistake earlier! (I've updated my page on the matter.)
Earlier I wrote that Θ1,1,k, Θ1,2,k, and Θ2,2,k are all winnable, but in fact Θ1,2,k is not winnable! (Unless k=1 or k=2, obviously.) Not sure how I missed that one earlier. Basically the computer can exploit the difference in lengths to set up a trap, much as how the computer can exploit the difference in sizes if you take two unequally-sized complete graphs and join them at a vertex.
This also means my question about subdivision now has an answer; the answer is no! I'm surprised, I really thought that one would turn out to be true.
Unfortunately this also means my claim to have checked all graphs of up to 8 vertices is also false, because the method I used assumed the winnability of Θ1,2,k. So actually my method was only valid up to 7 vertices. Maybe I'll try to redo the check for 8 vertices? I expect it to just be too difficult, though... :-/
-Harry
Earlier I wrote that Θ1,1,k, Θ1,2,k, and Θ2,2,k are all winnable, but in fact Θ1,2,k is not winnable! (Unless k=1 or k=2, obviously.) Not sure how I missed that one earlier. Basically the computer can exploit the difference in lengths to set up a trap, much as how the computer can exploit the difference in sizes if you take two unequally-sized complete graphs and join them at a vertex.
This also means my question about subdivision now has an answer; the answer is no! I'm surprised, I really thought that one would turn out to be true.
Unfortunately this also means my claim to have checked all graphs of up to 8 vertices is also false, because the method I used assumed the winnability of Θ1,2,k. So actually my method was only valid up to 7 vertices. Maybe I'll try to redo the check for 8 vertices? I expect it to just be too difficult, though... :-/
-Harry
