Some Questions — Question 31

Definitions and mathematical statement

For an infinite group $\Gamma$ with symmetric generating set $S\subseteq\Gamma\setminus\{1\}$, the Cayley graph $G=\operatorname{Cay}(\Gamma,S)$ has vertices $\Gamma$ and edges $\{x,xs\}$ for $x\in\Gamma$, $s\in S$. Its chromatic number $\chi(G)$ is the least number of colors in a proper vertex coloring, where adjacent vertices have different colors.

The source asks whether every infinite Cayley graph has a "$G$-invariant proper coloring" with exactly $\chi(G)$ colors, but does not define invariance. For the finite-color case $k=\chi(G)<\infty$, there are distinct formulations:

1. A deterministic coloring $c:\Gamma\to\{1,\ldots,k\}$ fixed by all translations would satisfy $c(gx)=c(x)$ for all $g,x\in\Gamma$. Such a function is constant because translations are transitive. Thus literal deterministic invariance is incompatible with proper coloring of a graph having an edge.
2. An invariant random coloring means a $\Gamma$-invariant Borel probability measure $\mu$ on \[ \mathcal C_k(G)=\{c\in\{1,\ldots,k\}^{\Gamma}:c(x)\ne c(xs)\text{ for all }x\in\Gamma,s\in S\}, \] where $(g\cdot c)(x)=c(g^{-1}x)$. The invariance condition is $\mu(g\cdot A)=\mu(A)$ for every Borel set $A$ and $g\in\Gamma$. A natural probabilistic reading asks whether such a $\mu$ always exists with $k=\chi(G)$, but the source does not explicitly include the word "random."
3. A measurable or Borel coloring of a specified group action or graphing, or an equivariant coloring that is a factor of an independent-label process, adds structures and constraints absent from the statement. These are not automatically the same existence question as item 2.

The source also writes $G$ for the graph, so it does not identify whether invariance refers to the chosen Cayley group's translations or the full graph automorphism group. Nor does it specify a finite generating set or finite chromatic number. The probability-space formulation above explicitly describes the usual countable, finite-color setting without silently imposing it on the full source.

The supplied summary reports examples in which measurable chromatic number exceeds ordinary chromatic number and says it did not verify a general $\chi(G)$-color theorem and that such a theorem "likely fails." No example, precise measurable model, or citation is supplied, and that tentative assessment does not resolve the invariant-random-coloring reading.

Short English statement

The question asks for an invariant proper coloring using the ordinary chromatic number of colors. A translation-fixed deterministic coloring cannot work, while a translation-invariant law on proper colorings is a different, natural interpretation. The source does not specify which meaning is intended, and its measurable-coloring summary does not settle that distinction.

Sources

• Local UnsolvedMath registry, permanent ID 1200031, exact source code catalogue entry, "Some Questions --- Question 31"; status partially solved, classification PARTIAL-PROGRESS.
• Abért, Some questions (2010), Question 31, https://www.renyi.hu/~abert/questions.pdf. The provenance records manual transcription of a public author-hosted PDF, accessed July 29, 2026; it says the 2010 list was inspected, while current status was not independently verified.
• The supplied research summary discusses measurable/Borel coloring numbers of Cayley graphs and graphings, reports unspecified examples exceeding ordinary chromatic number, and gives only a tentative "likely fails" assessment of the general claim. It supplies no named theorem, example, or authoritative external citation for a resolution of this exact question.