Consider an infinite integer lattice, or an infinite hexagonal lattice with unit length edges. Provided a set of $k$ possible vertex colors, is there a known largest possible minimum spacing that can be achieved between vertices of the same color? What about for three-dimensional integer lattice?



Achieving the largest possible minimum spacing between vertices of the same color in an integer lattice
Turning this question around, you can instead ask how many colours you need to ensure that no two points at distance at most $d$ receive the same colour. That is, add edges to your graph between all pairs of vertices at distance at most $d$: what is the chromatic number of this new graph?


If we join points at distance exactly $d$ instead of at most $d$, then this question has received quite a lot of attention. It is a famous open problem to determine the *chromatic number of the plane*, the chromatic number of $\mathbb R^2$ with edges between points at Euclidean distance 1. There are easy constructions to show that $4 \leq \chi(\mathbb R^2) \leq 7$, but nothing better is known.


The construction for the lower bound generalises to give $\chi(\mathbb R^n) \geq n+2$ for every $n$. The first exponential lower bound was proved by Frankl and Wilson. A set system can be embedded as a collection of 0-1 vectors, so that distances correspond to intersection sizes. Frankl and Wilson spotted that they could apply a result of theirs on forbidden intersection sizes to show that independent sets in their collection of vectors could not be too large, which was enough to prove that $\chi(\mathbb R^n) \geq (1.05+o(1))^n$.


