Z. Liu, L. Chew, M. Heule:

"Avoiding Monochromatic Rectangles Using Shift Patterns";

Talk: International Symposium on Combinatorial Search, Jinan, China; 2021-07-26 - 2021-07-30; in: "Proceedings of the Fourteenth International Symposium on Combinatorial Search", AAAI Press, 12 (2021), ISBN: 978-1-57735-870-1; 225 - 227.

Ramsey Theory (Graham and Rothschild 1990) deals with

patterns that cannot be avoided indefinitely. In this paper we

focus on a pattern of coloring a n by m grid with k colors:

Consider all possible rectangles within the grid whose length

and width are at least 2. Try to color the grid using k colors

so that no such rectangle has the same color for its four corners.

When this is possible, we say that the n by m grid is

k-colorable while avoiding monochromatic rectangles.

Many results regarding this problem have been derived by

pure combinatorial approach: for example, a generalization

of Van der Waerden´s Theorem can give an upper bound; it

was shown (Fenner et al. 2010) that for each prime power

k, a k2 + k by k2 grid is k-colorable but adding a row

makes it not k-colorable. However, these results are unable

to decide many grid sizes: whether an 18 by 18 grid is 4-

colorable is an example. This grid had been the last missing

piece of the question of 4-colorability, and a challenge prize

was raised to close the gap (Hayes 2009). Three years later,

a valid 4-coloring of that grid was found by encoding the

problem into propositional logic and applying SAT-solving

techniques (Steinbach and Posthoff 2012). That solution has

highly symmetric color assignments by construction: assignments

of red are obtained by rotating the assignments of

white around the center by 90 degrees, blue by 180 degrees,

and so on. By now, the k-colorability has been decided for

k 2 f2; 3; 4g for all grids.

Therefore, it is natural to ask, what about 5 colors? Applying

the aforementioned theorem (Fenner et al. 2010), the 25

by 30 grid is 5-colorable, but for other grids such as 26 by 26

the problem remains open. Like many combinatorial search

problems, the rectangle-free grid coloring problem is characterized

by enormous search space and rich symmetries.

Symmetry breaking is a common technique to trim down the

search space while preserving satisfiability. While breaking

symmetries between different solutions is definitely helpful,

breaking the so-called "internal symmetries" that is within a

specific solution has also been proved to be effective (Heule

andWalsh 2010). Enforcing observed patterns is also known

as "streamlining" (Gomes and Sellmann 2004) and "resolution

tunnels" (Kouril and Franco 2005) and has been effective to improve lower bounds of various combinatorial

problems including Van der Waerden numbers (Kouril and

Franco 2005; Heule 2017), Latin squares (Gomes and Sellmann

2004), and graceful graphs (Heule and Walsh 2010).

However, the rotation internal symmetry that Steinbach

and Posthoff applied cannot translate to 5 colors. In finding

a 4-coloring of the 18 by 18 grid, Steinbach and Posthoff

generated a "cyclic reusable assignment" for one color, and

rotated the solution by 90, 180, and 270 degrees to assign to

the remaining three. Rotation by 90 degrees does not apply

naturally when the number of colors are not multiples of 4.

Thus, to find a 5-coloring of 26 by 26, or rather, to find

a valid coloring for any number of colors k in general, an

internal symmetry that is applicable to all k is very desirable.

We found a novel internal symmetry that is unrestricted by

the number of colors k. Further analysis on this symmetry

gives further constraints on the number of occurrences of

each color. Factoring in these constraints, the search time for

G24;24 and G25;25 can be reduced to a few minutes. We also

attempted to solve the 26 by 26 grid; many attempts came

down to only 2 or 3 unsatisfied clauses, but none succeeded.

https://publik.tuwien.ac.at/files/publik_299257.pdf

Created from the Publication Database of the Vienna University of Technology.