Talks and Poster Presentations (with Proceedings-Entry):
Z. Liu, L. Chew, M. Heule:
"Avoiding Monochromatic Rectangles Using Shift Patterns";
Talk: International Symposium on Combinatorial Search,
- 2021-07-30; in: "Proceedings of the Fourteenth International Symposium on Combinatorial Search",
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.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.