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?
4
-
$\begingroup$ Rephrasing: what is the chromatic number of the $d^{th}$ power of the integer lattice (the graph with the same vertex set and edges between vertices at distance at most $d$)? $\endgroup$– Ben BarberCommented Nov 5, 2013 at 17:37
-
$\begingroup$ @BenBarber I am speaking of a Euclidean distance rather than a edge-wise distance, if that makes sense. Imagine, for example, that vertices of the same color repulse one-another as a function of their pairwise Euclidean distance, and we wish to color the vertices to minimize any such repulsive forces. After doing so with $k$ colors (as best we can) what is the minimum distance between vertices of the same color? $\endgroup$– NTaylorCommented Nov 5, 2013 at 17:47
-
$\begingroup$ In that case you want the chromatic number of the graph with edges between points at Euclidean distance at most $d$. Googling "chromatic number integer lattice" gives some promising results (and they appear to be focusing on the Euclidean case). One way to shed some light on this question is to embed set systems into $\mathbb{Z}^n$ as 0-1 vectors. The Frankl-Wilson theorem was used in this way to improve the bounds on the chromatic number of $\mathbb{R}^n$ for large $n$. $\endgroup$– Ben BarberCommented Nov 5, 2013 at 17:57
-
$\begingroup$ @BenBarber Thank you - those are some very promising leads. $\endgroup$– NTaylorCommented Nov 5, 2013 at 17:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
answered Nov 5, 2013 at 18:32
-
$\begingroup$ Wouldn't this be an easier instance than asking for the chromatic number of the plane since we restrict ourselves to vertices at defined locations in a lattice? $\endgroup$– NTaylorCommented Nov 5, 2013 at 18:47
-
$\begingroup$ It's different. It's easier because $\mathbb Z^n$ is simpler than $\mathbb R^n$, but it's more complicated because allowing distances less than $d$ too means that you have more edges to worry about. $\endgroup$ Commented Nov 5, 2013 at 18:51
-
$\begingroup$ I wonder if it's possible to come up with a lowerbound for the best one can do? BTW, I'll +1 you as soon as I have the requisite reputation. $\endgroup$– NTaylorCommented Nov 5, 2013 at 18:54