## [Computational Complexity] The 17x17 challenge. Worth \$289.00. This is not a ...

Expand Messages
• The 17x17 challenge: worth \$289.00. I am not kidding. 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
Message 1 of 1 , Nov 30, 2009
The 17x17 challenge: worth \$289.00. I am not kidding.

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.)

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:
1. For all c there is a finite set of grids a1xb1, ..., akxbk such that a grid is c-colorable iff it does not contain any of the aixbi (n x m contains a x b if a &le n and b &le m). We call this set of grids OBSc (OBS for Obstruction Set).
2. OBS2 = {3x7, 5x5, 7x3}
3. OBS3 = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}
4. OBS4 contains 41x5, 31x6, 29x7, 25x9, 9x25, 7x29, 6x31, 5x41
5. Exactly one of the following sets is in OBS4: 23x10, 22x10, 21x10.
6. Exactly one of the following sets is in OBS4: 22x11, 21x11, 21x10.
7. Exactly one of the following sets is in OBS4: 22x11, 22x10, 21x10.
8. Exactly one of the following sets is in OBS4: 21x13, 21x12, 21x11, 21x10.
9. Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17.
10. If 19x17 is in OBS4 then 18x18 might be in OBS4 . If 19x17 is not in OBS4 then 18x18 is not in OBS4 .
11. A chart of what we do and do not know about 4-colorings of grids is here.
12. 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 OBS4. 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 OBS4 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?
1. A Rutgers grad student named Beth Kupkin has worked on the problem: here.
2. A high school student (member of my VDW gang) Rohan Puttagunta has obtained a 4-coloring of 17x17 EXCEPT for one square: here.
3. SAT-solvers and IP-programs have been used but have not worked--- however, I don't think they were tried that seriously.
4. Here are some thoughts I have had on the problem lately: here.
5. 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.

--
Posted By GASARCH to Computational Complexity at 11/30/2009 12:14:00 PM
Your message has been successfully submitted and would be delivered to recipients shortly.