sniffnoy: (SMPTE)
So 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. :) )

sniffnoy: (SMPTE)
Obviously, I haven't been posting much here lately. Here's another entry for the "problem dump" series -- two math problems I don't really intend to work on (at least not at the moment). I'll probably put this up on my website later.

Actually, I'm a little surprised to find that I haven't written anything about this here earlier. Oh well. Here we go.

Let's consider the game of Snake; except instead of playing it on a grid, we're going to play it on an arbitrary finite [simple] graph. We assume the snake starts at length 1 -- the game begins by the "computer" (who acts adversarially) picking a starting spot for the snake and a starting spot for the fruit. When the snake consumes the fruit (and thereby grows by 1), the computer picks a new spot for the fruit, which cannot be somewhere currently covered by the snake. We'll say the player wins if the snake covers the whole graph. If the game goes on infinitely, I guess that's a draw, but we'll give it to the computer.

(Here are some obvious ones -- if a spanning subgraph of a graph is winnable, then so is the whole thing; any cycle is winnable, so so is any graph with a Hamilton cycle; in order to be winnable, a graph must have a Hamilton path. But like I said, I'm not going to put all my notes here.)

So the general question then is, for which graphs can the player always win? (Hence why I said draws go to the computer.) Now this question is not necessarily that concrete; there might not be any nice characterization. I have bunch of notes about necessary conditions and sufficient conditions for this, but I'm not going to list them all here. I do, however, have two specific questions about this that I'd like to ask.

So -- you'll notice I didn't give a totally formal specification of the rules above, and there's a reason for that. When you formalize the rules, you realize there's the question: Should a snake of length 2 be allowed to turn around? As in, move its head to the current location of the tail. If you write the rules in the obvious manner, this is entirely legal, but it seems kind of unintuitive. So we can have two variants of the game: The weak game, where this is allowed; and the strong game, where it is not. (Note that you could consider graphs with multiple edges, and say that then in the strong game you're allowed to turn around if there's a double edge; but I'm restricting to simple graphs for reasons you'll see shortly.)

There is at least one graph that is weakly winnable but not strongly winnable, namely, a path of length 3. So, question number one: Are there any other such graphs? I suspect the answer is no but have been unable to prove it. Hence the restriction to simple graphs -- if I'm right, then unless the "underlying simple graph" is P3, adding multiple edges simply won't affect anything. (And it's easy to see how it affects P3.)

Here's a second question. When I initially mentioned this problem to John, he suggested that whether a graph is winnable or not should depend only on its topology. But this is not so; I have examples of (weakly or strongly) winnable graphs that can be subdivided to be made non-winnable. However, I have been unable to find an example of a (weakly or strongly) non-winnable graph which can be subdivided to be made winnable. So, question number two: If a graph is non-winnable (weakly or strongly), is the same true of any subdivision of it? For this question I don't really have a good idea what the answer should be. My guess would be yes, but I wouldn't be all that surprised if someone found a counterexample.

By the way, someone -- I forget who, unfortunately -- suggested that you could also play Snake on infinite graphs, with the win condition being that you grow arbitrarily large (now it's only a "draw" if the game goes on infinitely but your size stays bounded). But that seems like a pretty different problem, so I'm not going to consider that here.

sniffnoy: (SMPTE)
What would happen to homotopy theory if we used a more general notion of homotopy?

Let me make a formal definition: Given topological spaces X and Y and continuous maps f,g:X→Y, we'll say f and g are C-homotopic if there exists a connected space Z with points z0 and z1 and a continuous map h:X×Z→Y such that h(x,z0)=f(x) and h(x,z1).

So, obviously, this is a more inclusive notion than our usual notion of homotopy. We can then talk about C-homotopy equivalence, C-contractibility, C-homotopy groups, etc. And certainly there are maps that are C-homotopic but not homotopic; let Y be connected but not path-connected, and consider two points in Y in different path components as maps from the one-point space.

But can we find less trivial examples of maps that are C-homotopic but not homotopic? What about examples that just straight up are *not* C-homotopic? What about examples of spaces that are C-homotopy equivalent, but not homotopy equivalent, as well as spaces that aren't C-homotopy equivalent at all? (Question I tried unsuccessfully to answer: Is the topologists's sine curve C-contractible?)

Do C-homotopy groups agree with the usual homotopy groups? Do our usual algebraic topology functors respect C-homotopy in addition to just homotopy? (I asked John about this, he suggested that cohomology at least probably should.)

I'm posting this here as idle speculation because really, I don't know topology very well; I don't know enough to try to answer this. (Maybe someone already has. John hadn't heard of such a thing, that much I can say.) I thought of asking MathOverflow... but I was afraid I wouldn't be able to understand any answer I got! So yeah, I'm posting this here.

sniffnoy: (Sonic)
UPDATED Oct 23 with some additional info. See the explanation of the *s for new summary.
UPDATED yet again Oct 25; if n is 16 mod 64, f(n)=4, and if n is divisible by 1024, f(n)≥5. Also if n is exactly divisible by 512 and has any prime factors that are 3 mod 4, f(n)≥5. It's all added to the summary.
ONE MORE THING Oct 29: If g(k) is the first appearance of color k, then for k≥3, g(k)≥2k-1+4, which proves that f(n)=O(log n).

I expect this is all already known (though I don't see any of these sequences -- whether you subtract off 1 from our convention or not -- in OEIS), but let's just write this all down anyway.

So the other day I encountered on the internet the following simple open problem I hadn't heard of before: Is there a finite coloring of the positive integers such that for all (m,n)≠(2,2), m+n gets a different color from m*n? The expected answer, of course, is no. (You could also do it as whole numbers if you add in an exception for (0,0) as well. Of course then this just means that 0 gets its own color and the rest is as before.)

Anyway I thought this was neat and pointed this out to Josh with no intention of actually thinking about this at all because I mean really, what would I do with it? I don't know anything about this sort of stuff. (Also, I have actual work to do.) But then he suggested: Obviously proving any finite coloring won't work would be too hard, but what if we just considered the greedy coloring (colors are the positive integers, each number gets the smallest color that doesn't violate the constraints from the previous one)? Could you at least show that ends up using infinitely many colors?

Well, after a bit of thinking and a bit of computation, I'm pretty sure the answer is "There is no way I have the time or knowledge to tackle this right now". But before I really stop thinking about this and get back to stuff I actually need to be doing, let me write down here what I have figured out so far about this greedy coloring.

Notation: f(n) will mean the color of n. I'll also just say "n gets m" to mean f(n)=m. I'm going to start my colors at 1 rather than 0, because that's what Josh did and so that's what I've been doing and I don't feel like changing it. (It also means that if you use the starting at 0 variant, and start your colors at 0 too, then 0 gets 0, and the rest is the same as without either sort of zero. However, I'll be excluding 0 as it's just inconvenient.)

Here then are the facts!

Firstly, unless n is 0 or 4 mod 16, f(n) is easily determined. If n is odd, f(n)=1, and conversely, if n is even, f(n)≥2. If n is 2 mod 4, or 12 mod 16, f(n) is 2. If n is 8 mod 16, f(n) is 3; more generally, if n is divisible by 8, f(n)≥3. It's only if n is 0 or 4 mod 16 that f(n) varies (and no, these do not seem to be periodic wrt some higher modulus -- these ones actually get bigger, after all!). If n is 4 mod 16, then f(n)≥2, as noted above; if n is 0 mod 16, then f(n)≥3, as also noted above. Furthermore, if n is divisible by 128, then f(n)≥4. I'll refer to the congruence classes mod 16 as "columns". The 4s column depends only on previous values of the 4s column (it can actually only "see" the 4s column, the odd columns, which are always 1, and the 12s column, which is always 2), while the 0s column depends on the previous values of both nontrivial columns (it can see all the columns).

Update 23 Oct: Also, if If n=16 (mod 32) and f(n)=3, then n=48 (mod 64). If n=4 (mod 16) and f(n)=2, then n=4 (mod 32) and n has no prime factors that are 3 mod 4.

Edit: So you can see what I'm talking about, here's the columns visually (top row in hex, * means it varies, starting at 1 instead of 0 for obvious reasons)


That * beneath the 4 is at least a 2. It is at least a 3 if the number is 20 mod 32, or has any prime factors that are 3 mod 4.
That * beneath the 0 is at least a 3. It is at least a 4 if the number is divisible by 128, and is exactly 4 if the number is 16 mod 64. It is at least 5 if the number is divisible by 1024, or is exactly divisible by 512 and has any prime factors that are 3 mod 4.

...that's about as far as pure reasoning gets me. But I wrote a simple C program to compute these numbers and computed up to 2^25. (Or, I suppose, 2^25+3, seeing as I can easily fill those in. Of course the program can go higher, but 2^25 was relatively quick while 2^26 was turning out not to be, so I stopped there.) So using this, let's look at when values of f first appear!

1 first occurs at 1.
2 at 2.
3 at 8.
4 at 16.
5 at 64.
6 at 1024.
7 at 4080.
8 at 32000.
9 at 9625536.
10 does not occur within the range of my computation.

What's going on here? No idea! But we can state the conclusion: The values of f really do grow slowly. Josh said f(n)=o(nε), which I assume is easy but have not bothered to verify. He suggested perhaps f(n)=o(log n), though I have to wonder if maybe it's even slower still (well, you know what I mean). In any case, getting lower bounds? Yikes.

Now you'll notice all the numbers above (save for the initial 1, 2, 8) are 0 mod 16. What if we look at the first occurrences in the 4s column? That gets us:

1 does not occur
2 at 4
3 at 20
4 at 36
5 at 1188
6 at 22932
7 at 389844
8 at 13197780
9 does not occur within the range of my computation.

Or, these are even slower. Note, by the way, that if we explicitly restricted attention to the 0s column instead, we'd never see 1 or 2, and we'd see 4 before 3 -- a 4 at 16 and a 3 at 32. That sort of non-monotonicity can't happen in the 4s column due to its limited "vision". Of course it can't happen in the 0s column either past that point so long as the 0s column continues to get the actual firsts.

Regarding my note that these are slower, let's actually compare the two lists above by merging them. If we do, the list goes:
First 1
First 2
First 2 in 4s column
First 3
First 4
First 3 in 4s column
[First 3 in 0s column, if we care]
First 4 in 4s column
First 5
First 6
First 5 in 4s column
First 7
First 6 in 4s column
First 8
First 7 in 4s column
First 9
First 8 in 4s column

The first few are irregular but starting with the first 6 there's a definite pattern evident in the order they mesh together. Why? What does this mean? I have no idea! And now, having written this down, I have no intention of thinking about it any further.


September 2017

17181920 212223


RSS Atom
Page generated Sep. 26th, 2017 07:11 am
Powered by Dreamwidth Studios