Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color. (The rectangles I care about have the sides parallel to the x and y axis.)
The 17x17 challenge: The first person to email me a 4-coloring of 17x17 in LaTeX will win $289.00. (I have a LaTeX template below.)
UPDATE: THE RESULTS ABOUT OBS_{4} HAVE CHANGED SINCE THE ORIGINAL POST SINCE BRAD LARSON EMAILED ME A 4-COL OF 21x10 and 21x11. UPDATE: BRAD LARSON EMAILED ME A 4-COL OF 22x10.
UPDATE- PROBLEM WAS SOLVED. See my arXiv paper on grid colorings OR
my Feb 8, 2012 post.
Why 17x17? Are there other grids I care about? We (We=Stephen Fenner and Charles Glover and Semmy Purewal) will soon be submitting a PAPER (see TALK for a superset of the slide-talk I've given on this paper) on coloring grids. Here are the results and comments:
- For all c there is a finite set of grids a_{1}xb_{1}, ..., a_{k}xb_{k} such that a grid is c-colorable iff it does not contain any of the a_{i}xb_{i} (n x m contains a x b if a &le n and b &le m). We call this set of grids OBS_{c} (OBS for Obstruction Set).
- OBS_{2} = {3x7, 5x5, 7x3}
- OBS_{3} = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}
- OBS_{4} contains 41x5, 31x6, 29x7, 25x9, 23x10, 10x23, 9x25, 7x29, 6x31, 5x41
- Exactly one of the following sets is in OBS_{4}: 21x13, 21x12.
- Exactly one of the following sets is in OBS_{4}: 19x17, 18x17, 17x17.
- If 19x17 is in OBS_{4} then 18x18 might be in OBS_{4} . If 19x17 is not in OBS_{4} then 18x18 is not in OBS_{4} .
- A chart of what we do and do not know about 4-colorings of grids is here.
- A Rectangle Free Subset of a x b is a subset of a x b that has no rectangles. Note that if a x b is 4-colorable then there must be a rectangle free subset of a x b of size Ceil(ab/4). We actually have a rectangle free subset of 17x17 of size Ceil(289/4)+1. Hence we think it is 4-colorable. For the rectangle-free subset see here. For the original LaTeX (which you can use for a template when you submit yours) see here. THIS IS WHY I AM FOCUSING ON 17x17--- BECAUSE I REALLY REALLY THINK THAT IT IS 4-COLORABLE. I could still be wrong.
What if 17x17 is not 4-colorable? Then nobody will collect the $289.00. Even so, if you find this out I would very much like to hear about it. I don't want to offer money for that since if your proof is a computer proof that I can't verify then its not clear how I can verify it. I also don't want to offer money for a reasonable proof since this may lead to having the Supreme Court decide what is a reasonable proof.
Can I get a paper out of this? FACT: If you get me the coloring and want to use it in a publication then that is fine. OPINION: It would not be worth publishing unless you get all of OBS_{4}. See next question.
What do you hope to get out of this? My most optimistic scenario is that someone solves the 17x17 problem and that the math or software that they use can be used to crack the entire OBS_{4} problem. If this happens and my paper has not been accepted yet then we could talk about a merge, though this is tentative on both ends.
Has there been any work done on this problem that is not in your paper?
- A Rutgers grad student named Beth Kupkin has worked on the problem: here.
- A high school student (member of my VDW gang) Rohan Puttagunta has obtained a 4-coloring of 17x17 EXCEPT for one square: here.
- SAT-solvers and IP-programs have been used but have not worked--- however, I don't think they were tried that seriously.
- Here are some thoughts I have had on the problem lately: here.
- There is a paper on the 3-d version of this problem: here.
Is Lance involved with this at all? When I gave a talk on grid colorings at Northwestern, Lance fell asleep.