11
$\begingroup$

Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have a facet in common, or equivalently¹, when $z := x-y$ and $-z$ are the only shortest vectors in the coset $z + 2L$ (such vectors $z$ are called "relevant"). Let $\chi(L)$ be the chromatic number of this graph (i.e., the minimal number of colors required to color the Voronoi diagram of $L$ such that two cells sharing a facet never have the same color).

Main question: Does this quantity $\chi(L)$ appear in the literature? Does it have a name? What are the standard facts about it?

Trivial observation: $\chi(L) \leq 2^d$ where $d$ is the dimension of $L$. (Proof: color $L$ by mapping $x\in L$ to its coset in $L/2L$.)

More specific question: What is the value of $\chi(L)$ for some standard lattices like the root lattices, their duals, and the Leech lattice?

Note: If $L$ is a root lattice, then the relevant vectors are precisely the roots. (In fact, this characterizes root lattices: Rajan & Shande, "A Characterization of Root Lattices", Discrete Math. 161 (1996), 309–314.)

Example observation: $\chi(A_n) \leq n+1$. (Proof: color $(x_0,\ldots,x_n)\in\mathbb{Z}^{n+1}$ such that $\sum_i x_i = 0$ by $\sum_i i x_i$ mod $n+1$.) This inequality is sharp as Fedor Petrov points out in a comment below. Even more trivially, $\chi(\mathbb{Z}^n) = 2$ (using a checkerboard coloring).

  1. Conway & Sloane, Sphere Packings, Lattices and Groups (Springer 3rd ed., 1999), theorem 10 of chapter 21.
$\endgroup$
  • $\begingroup$ $\chi(A_n)=n+1$, since the elements $0,x_0-x_i,1\leqslant i\leqslant n$, should have different colors. $\endgroup$ – Fedor Petrov Apr 11 '17 at 14:47
5
$\begingroup$

It's been a bit long in the making, but Mathieu Dutour Sikirić, Philippe Moustrou, Frank Vallentin and I just uploaded to the arXiv a paper on “Coloring the Voronoi tessellation of lattices” which answers some aspects of the above question. In particular, we computed the following chromatic numbers:

  • $n+1$ for the root lattice $A_n$ and its dual $A_n^*$,

  • the chromatic number of the half-cube graph for the root lattice $D_n$, and $4$ for its dual $D_n^*$,

  • $9,14,16$ for the root lattices $E_6,E_7,E_8$, and $16$ for their duals $E_6^*$ and $E_7^*$,

  • and $4096$ for the Leech lattice.

We also show that the greatest chromatic number of an $n$-dimensional lattice grows exponentially with $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.