Chromatic number of graphs of tangent closed balls

Update May 2016

I removed the updates in Oct 2015. I was trying to combine two copies of strongly regular ball packings to double the chromatic number. But it has been point out that my construction was buggy.

Previous examples obtained in January 2015

Inspired by Bodarenko's counter-example to the Borsuk conjecture, I recently find many ball packings whose chromatic number is significantly higher than the dimension. There tangency graphs are all strongly regular. A note is available on arXiv and here (up to date).

Here I list their parameters, dimensions and lower bounds (Hoffman) for the chromatic numbers. Many of these parameters are for the complement to the more famous graph, e.g. Higman-Sims graph.

• $(100, 77, 60, 56)$ (Higman-Sims graph), dimension 22, $\chi\ge 80/3$.
• $(105, 72, 51, 45)$, dimension 20, $\chi\ge 25$.
• $(120, 77, 52, 44)$, dimension 20, $\chi\ge 80/3$.
• $(126, 75, 48, 39)$, dimension 20, $\chi\ge 26$.
• $(162, 105, 72, 60)$ (Local McLaughlin), dimension 21, $\chi\ge 36$.
• $(175, 102, 65, 51)$, dimension 21, $\chi\ge 35$.
• $(176, 105, 68, 54)$, dimension 21, $\chi\ge 36$.
• $(176, 85, 48, 34)$, dimension 22, $\chi\ge 88/3$.
• $(243, 132, 81, 60)$ (Delsarte graph), dimension 22 $\chi\ge 45$.
• $(253, 140, 87, 65)$, dimension 22, $\chi\ge 143/3$.
• $(275, 162, 105, 81)$ (McLaughlin graph), dimension 22, $\chi\ge 55$.
• $(276, 135, 78, 54)$, dimension 23, $\chi\ge 46$.
• $(729, 520, 379, 350)$, dimension 112, $\chi\ge 621/5$.

Furthermore, there are two infinite families with high chromatic number (here $q$ is a prime power).

• $(q^3, (q+1)(q^2-1)/2, (q+3)(q^2-3)/4+1, (q+1)(q^2-1)/4)$ (complements to Hubaut's C20), dimension $q^2-q$, $\chi\ge q^2$.
• $((q^3+1)(q+1), q^4, (q^2+1)(q-1)q, q^3(q-1))$ (complement to the point graph of the generalized quadrangle $(q,q^2)$), dimension $q^3-q^2+q$, $\chi=q^3+1$.

Note that the last case is an equality. This is the first non-constant lower bound for $\chi-d$.

Hope this helps future improvement.

It's easy to form sets of five mutually-tangent spheres (say, three equal spheres with centers on an equilateral triangle, and two more spheres with their centers on the line perpendicular to the triangle through its centroid). Based on this, I think it should be possible to construct a set of spheres analogous to the Moser spindle [http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem] that requires six colors: spheres a, b, and c, where a and b have four mutual neighbors that are all adjacent to each other, a and c have another four mutual neighbors that are all adjacent to each other, neither a and b nor a and c are adjacent, but b and c are adjacent.

I have no idea how tight this lower bound might be, but it's at least better than four.

I would guess that the unit distance graph has a higher chromatic number than the tangency graph of a sphere packing in high dimensions, but this is surely an open question. Here are some known results:

The best known lower bound for the chromatic number of the unit distance graph of Euclidean n-space is by Raigorodskii (Electronic Notes in Discrete Mathematics 28 (2007) 273–280): $1.239\dots^n$.

On the other hand, the best upper bound for the chromatic number of the tangency graph of a packing of spheres in dimension n that I can think of is the following simple-minded one:

Let $\kappa_n$ denote the kissing number in n-dimensional Euclidean space. This is the maximum number of non-overlapping unit spheres that can touch some fixed unit sphere.

Then the chromatic number of the tangency graph of a sphere packing is at most $1+\kappa_n$. This is seen using a greedy colouring as follows: take a sphere of smallest radius. Since all spheres touching it have radius at least as large, their number is bounded above by $\kappa_n$. So we can colour this sphere and remove it from the graph. Repeat until the graph is empty.

By the Kabatiansky-Levenshtein bound (Problems of Information Transmission 14 (1978) 1–17), $\kappa_n\leq 1.32042\dots^{n}$. This is some distance away from the unit distance lower bound, and I guess it won't be easy to decide whether the unit distance chromatic number is really larger when the dimension is large.