17x17: Symmetric Single-Colorings and some Graph Theory

This is part of a series of posts is related to the “17x17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

In my last post I noticed that all of the smaller optimal single-colorings I generated showed diagonal symmetry, meaning that row 1 is the same as column 1, row 8 is the same as column 8, etc. It’s my hypothesis that all complete single-colorings are symmetrical in this way.

I decided to play with making the known 74-cell subset symmetrical by applying rotations and came up with this:

TODO: Insert google doc iframe

Figuring out an automorphism that would give me that diagonal symmetry was easier than inputting the original points into Google Spreadsheet. The colors show the hints that helped anchor the rotations. (I’m going to try to come up with an algorithm for permuting a grid into a symmetrical form).

It seems that symmetry is a very interesting quality in a graph, but when the Graph Theorists study symmetric graphs, they are looking at graphs with where (as I understand it)

any two linked vertices can be mapped onto any to other linked vertices, resulting in essentially the same graph

…which is much cooler. Another interesting thing to mention is that a valid coloring is essentially a hypergraph where the higher dimensional edges are the row/column relationship. It can be flattened into a graph in any number of ways, for example by connecting every colored cell with it’s four neighbors (possibly itself).

So up next for me is a brute force algorithm for single-colorings generated symmetrically.