UPDATE: Problem HAS been solved. See Feb 8, 2012 post. There IS a 4-coloring of 17x17 and also of 18x18. Can also see my arXiv paper on grid coloring.
Long time readers may recall that 17x17 problem that I posted on Nov 30, 2009 here. I am sometimes asked if the problem is still open. Alas it is. Is the bounty on it still available. Alas it is. Some thoughts and experiences
- See this for a different take on it.
- When I wrote the post not that many people tried it seriously. Because of the post and because Brian Hayes picked up on it (see here) many people have worked on it seriously. This is good in that I now know that its hard, but bad in that its still unsolved.
- A High School Student wanted a formal contract before showing me his alleged solution. I told him that if he posted a comment with the coloring ON MY BLOG I would have to pay up and would do so gladly. His solution didn't work anyway.
- Do I still think that 17x17 is 4-colorable? The problem is that this is a finite problem. The fact that nobody has found a 4-coloring MIGHT mean there isn't one. But it might just mean there are very few of them.
- As a pessimist I think that 17x17 IS 4-colorable. Why is that? The following three problems are open: is 17x17 4-colorable? is 17x18 4-colorable? is 18x18 4-colorable? If 17x17 was NOT 4-colorable then the rest would NOT be 4-colorable with no additional work. We will not be that lucky. By the same reasoning I think 18x18 is NOT 4-colorable. (There are a few other grids where we do not know if they are 4-colorable but not many.)
- Will future faster computers help? Maybe, but there needs to be a math breakthrough, even a small one, as well.
- Will future Quantum Computers help? I doubt anyone will go to the expense of building a quantum computer for the 17x17 grid problem. And I doubt there will be general-purpose quantum computers.
- The following problem is inspired by my problem but has not gotten that much attention: How hard is the following: Given (n,m,c) and a partial rectangle-free c-coloring of nxm, can it be completed to a total rectangle-free c-coloring of nxm. Should be NP-complete but I have not been able to prove this I also haven't tried that hard- Maybe I'll get a bright High School Student to do it and get some free lunches out of it (see here).
- JohnPaul Adamovsky claimed that they had a proof that 17x17 was NOT 4-colorable and had comments on it on my blog here. I could not make sense of his proof. I suspect he no longer believes this since recent email from him describes an approach to finding a 4-coloring. He also made an offer that if I bought him some type of computer (he says which type) he will solve the problem. I have declined it; however, I offered to do a post on updated status of the 17x17 problem so he could make a comment on it offering it to others (I am doing that NOW). Note that if he posted on my older posts very few people would see it. He did not respond kindly to my offer; however, we'll see if he comments.
I gave a talk on grid colorings at an Algorithms and Theory of Computation Day that Zachos invited me to in New York.
A the end I had the following exchange with Lane Hemaspaandra who had also given a talk.
LANE: What does this have to do with Algorithms or Theory of Computation?
BILL: I could make something up but I respect you and the audience too much for that. The answer is NOTHING.
LANE: Then why are you giving a talk on it at Algorithms and Theory of Computation day?
BILL: Because Zachos invited me. You could ask why he invited me, but I think it is because he knows my parents live in the area so I would be a cheap date- no housing costs.
OTHER AUDIENCE MEMBER: Actually this material does have applications. This is part of Ramsey Theory and there is an entire website of applications of Ramsey Theory to Computer Science.
BILL (Thinking- there's ANOTHER one aside from mine? I should take a look at it) OH- that's good to know- what is the pointer to it?
OTHER AUDIENCE MEMBER: Its http://www.cs.umd.edu/~gasarch/ramsey/ramsey.html. Oh- that's you! (READERS- see here.)
BILL: YES, Ramsey Theory has had applications to computer science and that's great! However, I am not going to make the following incorrect claim: (1) Ramsey theory has had apps to CS, (2) The Grid problem was inspired by Ramsey Theory. Hence (3) The Gird problem has apps to CS. That would be bad logic.