Another question about Snake
Jun. 30th, 2015 03:22 amSo do you remember a while ago I posted some questions about the game of Snake? Well, here's another one. Or perhaps I should really say, here's a rephrasing of one of them.
The broad question about Snake, which earlier I wrote might just be too broad to answer, was "Which graphs are winnable?" (Weakly or strongly.) But it is possible -- not likely, I don't think, but possible -- that this might have a not-too-complicated answer.
Let's reformulate the question first. If a graph has a spanning subgraph which is winnable, then the graph is winnable. Hence, rather than focusing on all winnable graphs, let's focus just on minimal winnables -- ones where deleting any edge renders the graph unwinnable. (Note: I'm going to assume the strong game unless I say otherwise.) Characterizing these would characterizing all winnable graphs, as a graph is winnable iff it contains some minimal winnable.
Then so far I've only managed to find a few types of minimal winnable graphs! And, more generally, every winnable graph I know of contains one of these as a spanning subgraph. There are of course the trivial ones -- the zero-vertex graph, the one-vertex graph, the path P2. But the interesting ones are the following:
1. For n≥3, the cycle Cn. (In the weak game, we should restrict to n≥4, as there C3 is not minimal.)
2. For n≥3, two copies of Kn joined at a vertex. (In the weak game, we should instead say n≥2, as n=2 yields the path P3.)
3. For 1≤i≤j≤k, define Gi,j,k to be the graph consisting of two vertices and three paths between them, with i, j, and k vertices in the interior of the three paths (respectively). Then G1,1,k, G1,2,k, and G2,2,k are examples of minimal winnable graphs.
So, the question: Could this possibly be all of them? It seems unlikely, but it might just be possible. I have in fact verified that these are all of them up to 8 vertices, so any counterexample will have to be at least 9 vertices, unless I've messed up.
EDIT 4 July 2015: I may indeed have messed up about the 8-vertex case. I'm certain about the 7-vertex case, though. Will update if I fully solve the 8-vertex case. (9-vertex is out of reach, I think.)
Note that a positive answer to this question would also imply that subdivisions of unwinnable graphs are unwinnable, answering that question from the previous post. (It would also answer the question of whether weak and strong winnability coincide aside from P3, but that's because this proposition essentially just includes that; it isn't a nontrivial implication.) I should say, if this is true, I don't expect it to be at all easy to prove; it's not actually something I expect at all to solve...
(I will update my website with all this later.)
(Also, "minimal winnable" is really fun to say. :) )
-Harry
The broad question about Snake, which earlier I wrote might just be too broad to answer, was "Which graphs are winnable?" (Weakly or strongly.) But it is possible -- not likely, I don't think, but possible -- that this might have a not-too-complicated answer.
Let's reformulate the question first. If a graph has a spanning subgraph which is winnable, then the graph is winnable. Hence, rather than focusing on all winnable graphs, let's focus just on minimal winnables -- ones where deleting any edge renders the graph unwinnable. (Note: I'm going to assume the strong game unless I say otherwise.) Characterizing these would characterizing all winnable graphs, as a graph is winnable iff it contains some minimal winnable.
Then so far I've only managed to find a few types of minimal winnable graphs! And, more generally, every winnable graph I know of contains one of these as a spanning subgraph. There are of course the trivial ones -- the zero-vertex graph, the one-vertex graph, the path P2. But the interesting ones are the following:
1. For n≥3, the cycle Cn. (In the weak game, we should restrict to n≥4, as there C3 is not minimal.)
2. For n≥3, two copies of Kn joined at a vertex. (In the weak game, we should instead say n≥2, as n=2 yields the path P3.)
3. For 1≤i≤j≤k, define Gi,j,k to be the graph consisting of two vertices and three paths between them, with i, j, and k vertices in the interior of the three paths (respectively). Then G1,1,k, G1,2,k, and G2,2,k are examples of minimal winnable graphs.
So, the question: Could this possibly be all of them? It seems unlikely, but it might just be possible. I have in fact verified that these are all of them up to 8 vertices, so any counterexample will have to be at least 9 vertices, unless I've messed up.
EDIT 4 July 2015: I may indeed have messed up about the 8-vertex case. I'm certain about the 7-vertex case, though. Will update if I fully solve the 8-vertex case. (9-vertex is out of reach, I think.)
Note that a positive answer to this question would also imply that subdivisions of unwinnable graphs are unwinnable, answering that question from the previous post. (It would also answer the question of whether weak and strong winnability coincide aside from P3, but that's because this proposition essentially just includes that; it isn't a nontrivial implication.) I should say, if this is true, I don't expect it to be at all easy to prove; it's not actually something I expect at all to solve...
(I will update my website with all this later.)
(Also, "minimal winnable" is really fun to say. :) )
-Harry
