(UPDATE- 17x17 WAS solved, as was 18x18. See my arXiv paper on grid coloring and/or my post on Feb 8, 2012).
One of my former high school students emailed me because he was excited that my 17x17 posting was picked up by another blogger: here Is that worth being excited about? Will it make me a celebrity? Will it get me on THE COLBERT REPORT or THE DAILY SHOW? I doubt it.
Many readers commented on my last post. These comments have lead to two corrections- my chart had typos, and the paper had a typo in an equation. The other objections raised were (I think) incorrect; however, I could be wrong. In THIS post I will answer all of the questions in the last post. If there are remaining questions, please post.
- The typos in the chart were fixed. THANKS for the corrections.
- The equation that Aaron Sterling pointed out was incorrect had a typo. THANKS Aaron. That should be fixed soon.
- The Obstruction set raised alot of questions. OBSc is NOT the set of all non-c-colorable grids. It is the set of all MINIMAL non-c-colorable grids. More precise: if nxm is in OBSc then nxm is NOT c-colorable but both (n-1)xm and nx(m-1) are c-colorable.
- Sky thinks 9,10,11 are in conflict. I corrected the chart so that may no longer be an issue, but if it is, please comment.
- Grid coloring is not related to coloring planar graphs. Grid coloring problems can be rephrased at hypergraph coloring problems. I doubt this is helpful, but I could be wrong.
- Why $289.00? Because 17x17=289. I originally thought I would offer $2.89 but Lance pointed out that that might not be enough to generate interest. Then I thought $28.90, but Lance again thought that would not get people interested. $289.00 seems just about right to get people interested but not break the bank of Gasarch. The person who won't give away the answer fo $289.00--- will you take $2.89 instead? How about $28.90?
- dut asks if the 74-sized Rect Free Subset is the smallest there is, or could there be one of sized 73. Actually we could just take out one element and get a 73-sized Rect Free Subset. I think dut meant to ask: in a 4-coloring do we know a number x such that no color appears less than x times? YES. Lets say (and this is true but probably can be improved) that there is no Rect Fres set of sized 80 of 17x17. Then the smallest possible number of times a color can appear can easily be lower bounded. li> One of the Anon posits that its impossible since this person thinks you can't have a 73-sized Rect Free Set. Alas, my original post had a 74-sized Rect Free Set. In fact, thats why I think you CAN 4-color 17x17. I look at it as a barrier result: All of the techniques to show a grid can't be c-colored used rect free sets. Hence 17x17 (and the others) will not be able to be proven not 4-colorable using our techniques. Hence new techniques are needed. Not quite as impressive as Oracles, Natural Proofs, or Algebraization.
- Scott claims that my claims are riddled with errors. Scott- please either point out an error or post that you are mistaken. Clearly the CHART was riddled with errors, but has been corrected.
- I agree with commenter after David Benson who would like to know what David Benson did. David Benson- please elaborate so we can see what you did and if its right.