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.
  • $\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

Your Answer

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

Browse other questions tagged or ask your own question.