15
$\begingroup$

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices are the ring of integers of a certain number field K endowed with a complex absolute value ||, and in which x and y are adjacent if and only if |x-y| = 1.

This made me realize I know very little about the chromatic numbers of infinite Cayley graphs, and too my surprise, I wasn't able to find much in the literature!

So here's a sample question. Let A be a finitely generated free abelian group, let S be a finite subset of A closed under negation, and let G be the Cayley graph whose vertices are the elements of A and where a,b are adjacent if and only if |a-b| lies in S.

For every integer N, G has a quotient G/N, a finite Cayley graph whose vertices are A/NA and whose edges are given by the images of S in A/NA. (Maybe better to take N large enough so that no element of S lies in NA, so G/N has no loops.)

Evidently a coloring of G/N pulls back to G, so we get an inequality of chromatic numbers

$\chi(G) \leq \chi(G/N)$.

My question is: is it always the case that

$\chi(G) = \inf_N \chi(G/N)$?

In other words: if G has a k-coloring, does it necessarily have a periodic k-coloring?

(You might think of $\inf_N \chi(G/N)$ as the chromatic number of a profinite Cayley graph.)

I don't even know how to do this for A=Z!

$\endgroup$
  • $\begingroup$ Do you want $S$ to be finite? $\endgroup$ – verret Jul 10 '18 at 21:09
  • $\begingroup$ Totes. I have edited. $\endgroup$ – JSE Jul 10 '18 at 21:20
  • $\begingroup$ This has a lot of the feel of asking whether there's a single shape that tiles the plane only aperiodically, although clearly the two problems aren't strictly equivalent. $\endgroup$ – Steven Stadnicki Jul 10 '18 at 23:18
  • 2
    $\begingroup$ I asked a particular case of this question here, where $A$ is a Euclidean lattice and $S$ the set of Voronoi neighbors of the origin, I obtained a number of results in this are last year with Mathieu Dutour and Frank Vallentin which we are still in the process of writing down, but I hope to upload them to the arXiv soon. All of our optimal colorings happen to be periodic but we don't know if there's a general reason. $\endgroup$ – Gro-Tsen Jul 11 '18 at 0:12
  • $\begingroup$ @Steven Why 'single' shape? It more seems to me that the answer will be no, because there are tiles that only tile aperiodically. Also, I would rather reduce the Domino problem to the question: mathworld.wolfram.com/WangsConjecture.html $\endgroup$ – domotorp Jul 11 '18 at 10:37
7
$\begingroup$

Here's an answer for $A = \mathbb Z$ (assuming that $S$ is finite):

Let $c$ be an optimal (i.e. using the minimal number of colours) colouring of $\mathrm{Cay}(\mathbb Z,S)$ and let $k > \max S$. The degrees in $\mathrm{Cay}(\mathbb Z,S)$ are bounded, hence $c$ uses a finite number of colours.

This means there are only finitely many possibilities for the sequence $(c(n+i))_{0 \leq i \leq k}$ and hence there are $n_1,n_2 \in \mathbb Z$ such that $n_2 > n_1 + k$ and $c(n_1+i) = c(n_2 + i)$ for $0 \leq i \leq k$. Without loss of generality assume that $n_1 =0$, $n_2=l$

Define a colouring $d$ by $d(n) = c(n \mod l)$. This clearly is periodic. Since $k > \max S$ and $c(i) = c(l + i)$ for $0 \leq i \leq k$, the neighbours of any vertex $n$ have the same colours in $d$ as the neighbours of $(n \mod l)$ have in $c$, whence the colouring is proper.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is also the same proof given by Eggleton, Erdos, and Skilton in "Coloring Prime Distance Graphs", Graphs and Combinatorics 6, 17-32 1990, theorem 2. $\endgroup$ – Gjergji Zaimi Jul 11 '18 at 2:43

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.