Cuadrícula de colores

Actualización : ahora se conoce el conjunto de obstrucciones (es decir, la "barrera" NxM entre los tamaños de cuadrícula colorable e incolorable) para todos los 4 colores sin rectángulo monocromático .

¿Alguien tiene ganas de probar 5 colores? ;)

La siguiente pregunta surge de la teoría de Ramsey .

Considere una coloración del gráfico de cuadrícula n -by- m . A existe siempre que cuatro celdas con el mismo color estén dispuestas como las esquinas de algún rectángulo. Por ejemplo, ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , y ( 1 , 0 ) formar un rectángulo monocromática si tienen el mismo color. Del mismo modo, ( 2 , 2 ) , ( 2 , 6 ) $k$$n$$m$monochromatic rectangle$(0,0), (0,1), (1,1),$$(1,0)$$(2,2), (2,6), (3,6),$ and $(3,2)$ form a monochromatic rectangle, if colored with the same color.

Question: Does there exist a $4$-coloring of the $17$-by-$17$ grid graph that does not contain a monochromatic rectangle? If so, provide the explicit coloring.

Some known facts:

• $16$-by-$17$ is $4$-colorable without a monochromatic rectangle, but the known coloring scheme does not appear to extend to the $17$-by-$17$ case. (I'm omitting the known $16$-by-$17$ coloring because it would very likely be a red herring for deciding $17$-by-$17$.)
• $18$-by-$19$ is NOT $4$-colorable without a monochromatic rectangle.
• $17$-by-$18$ and $18$-by-$18$ are also unknown cases; an answer to these would be interesting as well.

Disclaimer: Bill Gasarch has a $289 (USD) bounty on a positive answer to this question; you can reach him through his blog. A note on etiquette: I'll make sure he knows the source of any correct answer (should one arise).

He brought it up again during a rump session at Barriers II, and I find it interesting, so I'm forwarding the question here (without his knowledge; though I highly doubt he would mind).

Some of you are probably aware of this, but the 17 x 17 coloring problem has been solved by Bernd Steinbach and Christian Posthoff. See Gasarch's blog post here.

This is not really an answer to the question, but I've encoded the 17x17 4-coloring problem as a 4-CNF (in the standard DIMACS format for SAT-solvers) and uploaded it here. If anyone has access to a good SAT solver (and a supercomputer!) maybe we can make some progress.

Note: in my encoding, if gridpoint $(i,j)$ is assigned color $c \in \{0,1,2,3\}$, then the variable $(17i+j+289c+1)$ takes the value $1$, and $0$ otherwise.

This is not a real answer, either. Certainly the problem here is the presence of an astronomical number of symmetries, which fool even the best SAT solvers on the best supercomputers. Such symmetries map solutions to solutions and non-solutions to non-solutions: in this case probably there is an immense number of almost-solutions (i.e. assignments satisfying all but a small amount of clauses), each of which can be obtained by any other applying a proper symmetry. Hence the solver wastes an enormous amount of time trying each of these almost-solutions, while in a certain sense they are all the same.

Exploiting symmetries (see this paper) should be an avenue to explore in order to attack this hard 17x17 instance and make some progress on it. I wonder if anyone already tried to do so.

Again, not a real answer, but anyway, here are some thoughts on adopting graph colouring algorithms for this problem.

Let us say that a set $I$ of grid positions is an independent set if set $I$ does not contain all four corners of some rectangle. Define a maximal independent set in the obvious way. Now the following are equivalent claims:

1. $n$-by-$m$ grid can be coloured with $k$ colours.
2. $n$-by-$m$ grid can be covered with $k$ independent sets.
3. $n$-by-$m$ grid can be covered with $k$ maximal independent sets.

Now, the interesting thing is that covering with independent sets can be done in time $\log k\ \text{poly}(nm)2^{nm}$ using fast covering product algorithm (Björklund et al. 2007). This is certainly is an improvement over trivial $k^{mn}$ algorithm, though $2^{289}$ seems still unsurmountable.

If the family of all (maximal) independent set has sufficiently nice structure, it might also be possible to fine-tune the covering product algorithm.

The 21x12 grid is 4-colorable without monochromatic rectangles, as well !!!

See last Bernd Steinbach's post on Gasarch's blog!

This is Bill Bouris. Hi, Dan. I'm working on a program that searches for a suitable 17x17 matrix which exhibits no-4-coloring according to Ramsey's Theory. I use a positional matrix depicting all connections between points and fix the main diagonal and allow the top row of the matrix to run through all of the possible 16choose8 combinations; I capture only the matrices that pass regarding the following criteria... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB, etc., then I sweep through the matrix using the next weakest criteria... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB, etc. for a total of 32 sweeps until the computer fills in the coloring automatically. I've noticed that there's a possible candidate per every 400 matrices out of a total 12780, and it takes .95 hours to find the candidate or 1 per every 8.644 seconds. It's coming along, but I don't have much time to program it... as I work full-time. We should work together... I could use the $289.00!