Rectangle Free Grid Coloring - 21x12 and 18x18 Grid With Four Colors

As Steinbach already has posted his solution on Computational Complexity, I give an eye compatible version here ...

18x18 Grid With Four Colors


Rectangle Free Four Coloring of 18x18 Grid, found by B. Steinbach and C. Posthoff

21x12 Grid With Four Colors

Rectangle Free Four Coloring of 21x12 Grid, found by B. Steinbach and C. Posthoff

For a given complete bipartite graph K(m,n) you have to color its edges with c (e.g. c=4) colors. If you find a coloring such that there is no monochromatic rectangle in K(m,n) then you will have a rectangle free c-coloring of K(m,n). A grid is defined by the adjacency matrix of K(m,n). Each element is a number that indicates the edge color. Figures from above represents such a matrix with m=21 rows and n=12 columns. There are no four points forming a same colored rectangle such as you can see on the right figure.

The Zarankiewicz-Problem is a subproblem of the Grid Coloring Problem. Zarankiewicz asks for the minimum number of edges you have to insert into an empty bipartite graph such that there will be formed a rectangle as subgraph. Due to the pigeonhole principle the number of monochromatic edges of one color has to meet [mn/c] in the wanted four-coloring. If it does not then the Grid will not be c-colorable without monochromatic rectangles. Hence you have to solve the Zarankiewicz Problem for disproving a c-coloring of a grid.

B. Steinbach was able to solve the last open problems in the class of four-colorings (17x17, 17x18, 18x17, 18x18, 21x12), so he also found the bipartite Ramsey Number BR(2,4)=19 (similar to Ramsey Numbers, just take complete bipartite graphs with monochromatic bicliques). He worked together with Christian Posthoff on these problems. I was lucky to take part in this progress, even though I only was a witness. On one day I asked Bernd Steinbach again, if he had found some new results on the four coloring of the 21x12 problem. I knew that he again subjected a SAT solver to a very deep interrogation on the previous day. So Steinbach was speaking without any emotion about fifteen minutes that everything had been failed, what actually was the normal answer as always, and he finished with a little smile: "then he (SAT solver) got it".

First we really had our doubts and we were about to develop algorithms to prove that there could not be any 4-coloring. Well, my doubts were derived from Steinbach, admittedly I had no idea how to solve this problem. B. Steinbach created a very special sub-solution, which involved an ordered solution of the 21x12 Zarankiewicz-Problem, of course.

But the sub-solution was much more complicated. Steinbach explained it to me on the same day, but the "head" of that sub-solution looked very chaotic to me. After I understood I was stunned again by the system of chaos. O.k., I have to stop here for the sake of fairness. Steinbach will publish all the details on it soon but it will take some time. He did a great work, you will like it.

--

I have been playing around with the 21x12 solution to find the relationship between the color classes and the reduced latin squares of order 4, according to the Zarankiewicz Problem (see my upcoming paper). You will recognize the structure in the following pictures:


Each color class has been sorted, I use always the red color for the sake of readability. You also can see the Slot Architecture (matrix head (4,4,4) partition). The next figures show the structure of the four reduced latin squares in the adjacency matrix. One 3-bit pattern has to be expanded to three 2-bit patterns (see my upcoming paper).


As I worked out in my paper, the position of the last bits (highlighted) can be written in a tableau with four rows and four columns, so the Reduced Latin Squares of Order 4 are obtained:

The last three reduced latin squares belong to the same isotopy class (also isomorphic in this case, and relabeling means switching columns). Well, these structures are very interesting, but I have to make a break here. I hope the pictures are inspiring enough.
--
Upcoming Paper: B. Steinbach, Ch. Posthoff: "Solution of the Last Open Four-Colored Rectangle-free Grid - an Extremely Complex Multiple-Valued Problem", 43rd International Symposium on Multiple-Valued Logic (2013), submitted.