Chromatic number of Q5 and Q7

This webpage contains the source code of the program mentioned in my diploma thesis and the paper On the chromatic number of real and rational spaces, Geombinatorics 18, 53-66 (2008). The diploma thesis contains only the Q7 construction.

See wikipedia for more information about the problem of coloring R2. We are interested in the extension of the problem to other spaces, namely to the 5-dimensional and 7-dimensional Euclidean spaces Q5 and Q7 of points with rational coordinates.

The program is under GPL.

The program proves that the chromatic number is at least 8 for Q5 and at least 15 for Q7. For more information about the algorithm see the comments in the source file. The description of the usage is written to console when the program is started with no command-line parameters.

About the constructions

A lower bound b on the chromatic number of some graph G is proven by showing that with appropriately assigned weights, every independent set has weight smaller than w(G)/(b-1).

Dimension 7

The graph is the distance-2 graph whose vertices are the union of:
  1. points with three coordinates with absolute value 1 and four zero coordinates, weight 1000
  2. points with all coordinates with absolute value 1, weight 1
This was inspired by the construction from a paper by Larman and Rogers. They used the characteristic vectors of the 7 lines of the Fano plane with all possible combinations of signs. These are 56 vectors of dimension 7 with exactly three coordinates of absolute value 1 and four zero coordinates. They showed that if we use 2 as the forbidden distance, the largest independent set has size 4. This not only proves that the chromatic number is at least 14, but it is very near to proving that 15 colors are needed.
As a consequence, the largest independent set in our graph uses at most 20 out of the 280 vertices of type 1. The type 2 vertices have many neighbors among the vertices of type 1 and also many edges between themselves. With their help, the weight of the heaviest independent set is slightly smaller than w(G)/14.

Dimension 5

The graph is the distance-4 graph whose vertices are the union of:
  1. points with one coordinate with absolute value 2 and four zero coordinates, weight 2385
  2. points with three coordinates with absolute value 2 and two zero coordinates, weight 2140
  3. points with four coordinates with absolute value 1 and one zero coordinate, weight 381
  4. points with three coordinates with absolute value 1, one with 3 and one zero coordinate, weight 149
It has been some time since I found this construction, so my memories may not be very precise. The search consisted of trying many similar constructions and then trying different assignments of weights on the promising ones.
Some of these were generalizations of the constructions from papers by Matthias Mann and his data files that were available online, but seem not to be available anymore. The constructions contain large sets of vertices that differ from each other only by permuting and changing the signs of the coordinates. The generalization consisted of using all the vertices obtainable by permuting and changing the signs.
Joseph Culberson's Graph Coloring Programs were a great help in removing candidates that could be colored with fewer than 8 colors.