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$
7
  • $\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$ 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
  • 1
    $\begingroup$ In the case of two-colorings, the answer is yes, and the proof is fairly straightforward. Here's the idea. Suppose c is a proper two-coloring, where the codomain of c is {0,1}. For simplicity, assume that S generates A. Without loss of generality, assume that c(0)=0. (For if not, then reverse the colors.) Then c is itself a periodic two-coloring. If S does not generate A, then first restrict c to the subgroup generated by S, and then extend to all of A. For > 2 colors, this logic no longer works, and the problem seems to be much more difficult. $\endgroup$
    – Mike Krebs
    Oct 13 '20 at 0:08
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.

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