Mittwoch, 22. Februar 2012

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

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

21x12 Grid With Four Colors

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

Monochromatic Rectangle in 18x18 Grid 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:

21x12 grid coloring - sorted solution 121x12 grid coloring - sorted solution 221x12 grid coloring - sorted solution 321x12 grid coloring - sorted solution 4
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).
21x12 zarankiewicz problem - sorted solution 121x12 zarankiewicz problem - sorted solution 221x12 zarankiewicz problem - sorted solution 321x12 zarankiewicz problem - sorted solution 4

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:
reduced latin squares of order 4
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.

Zarankiewicz Problem and Algorithmic Approaches

Seminar Paper on Overflow Algorithm (english)
Download "An Algorithmic Approach for the Zarankiewicz Problem"  
(formerly "Algorithmic Approaches for the Zarankiewicz Problem")
published at the 10th International Workshop on Boolean Problems:
(29.10.2012: Some corrections to the printed version, e.g. number of assignments with respect to row and column permutations)

Presentation on Overflow Algorithm (english)
Download Presentation Slides "An Algorithmic Approach for the Zarankiewicz Problem"

Seminar Paper (german)
Download "Algorithmische Betrachtungen zum Zarankiewicz-Problem"
(29.10.2012: "Solution of the Last Open Four-Colored Rectangle-free Grid" and "The Many Formulae for the Number of Latin Rectangles" added to list of literature)
(28.08.2012: number of assignments with respect to row and column permutations in section 1.2 corrected, Table 1.2 extended)
(31.05.2012: proof on relative runtime asymptotic estimation reworked)
(07.05.2012: time benchmarks on page 11 fixed due to "bug")

Overflow and Slot-Algorithm
Download Source Code in C++ // including getopt library by Ludvik Jerabek
(06.09.2012): small improvement on row incrementing (~5% speedup) and some code style
(07.05.2012: upper bounds for maximum of subgrids were partially wrong :/)
// The solution matrix "PrevResults" does not contain the optimal value for 16x16 (unknown)

Seminar Paper - LaTeX/Gnuplot/processing
Download Source

During the last few months I have been working on the Zarankiewicz Problem for my seminar paper. My part was to develop some algorithms, and initially I was supposed to do this using CUDA. After some trials I decided to return to the CPU side, because the problem comes from the extremal graph theory. As far as I know it is even a problem to find the locality of such problems. Actually it even was difficult for me to write a decent and exact algorithm on the CPU side.

In my work you will find two algorithms. The first one is the Overflow Algorithm which works non-recursively and returns the global maximum of edges of the C4-saturated subgraph of K(m,n) (complete bipartite graph). Furthermore I show some ideas for optimization, but they are too savagely and make the algorithm inaccurate. Nevertheless, some nice structure information leads to an interesting connection with the slot architecture of the second algorithm.

The second algorithm is a greedy one called Slot Algorithm. The key idea is from B. Steinbach; he is my supervisor in this work. Different structure information had been used, however, the problem insists to be a beast. I could not finish the Slot Algorithm as I would have liked to do. There are many open questions about the bit/edge pattern hierarchy and how bit patterns of different sizes interact with each other.

Related Posts:
Rectangle Free Grid Coloring of 21x12