When are the 3-colorings of vertex subsets uncorrelated?

Question

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

• Does this property have a standard name in the literature?
• Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, does not give $C_M$ uncorrelated with $C_A$; I have not identified the maximal subset(s) of $V$ whose colourings are uncorrelated with $C_A$.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$ — slightly larger than the union of the black and grey vertices — but beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.

Answer 1

Old question and OP probably knows this stuff already, but I thought I'd address it in detail in case someone else comes across it. What you describe is closely related to various notions of irreducibility or mixing in dynamics, especially symbolic dynamics, where the underlying graph is generally an (undirected) Cayley graph of an infinite, finitely generated group.

Symbolic dynamics concerns the natural shift action of a countable group $G$ on the full shift $\mathcal{A}^G$ where $\mathcal{A}$ is a finite set. A point in the full shift is an infinite configuration $x: G \to \mathcal{A}$. Any full shift with the $\text{discrete}^G$ topology is a compact, zero-dimensional metric space on which $G$ acts by homeomorphisms. More precisely, you study the behaviour of the shift action on subshifts, which are the closed, shift-invariant subsets $X$ of the full shift. Any subshift can be characterized by the set of finite configurations that do not appear in any point $x \in X$---that is, the set of $w: V \to \mathcal{A}$, $V \subset G$ finite, i.e such that $x|_V \neq w$ for any $x \in X, g \in G$.

For instance, you can consider the $3$-coloured chessboard, the subshift of all proper vertex $3$-colourings of (the standard Cayley graph of) $\mathbb{Z}^2$. This is an example of a (sub)shift of finite type (SFT), which means that it can be characterized by a finite set of forbidden finite patterns. In the example of $3$-colourings of $\mathbb{Z}^2$, there are six patterns with two vertices each, specifically three horizontal and three edges with the same colour on each incident vertex.

A subshift is called irreducible or topologically mixing if any two permitted finite configurations can appear in the same infinite configuration as long as they are far enough apart. More precisely: we say that a subshift $X \subset \mathcal{A}^G$ is irreducible if for any finite, nonempty $U, V \subset G$, there is some finite, nonempty $W \subset G$ such that for any $x, y \in X$, and any $g \in G \setminus V U^{-1}W$, there exists $z \in X$ such that $z|_U = x|_U$ and $(g \cdot z)|_V = y|_V$. $X$ is strongly irreducible if some fixed $W$ works for all $U,V$.

E.g. on $\mathbb{Z}^2$, with the shift action denoted $T$, a subshift $X$ is irreducible if for any $n \geq 0$, there exists $r(n) \geq 0$ such that for any $x,y \in X$ and any $k,\ell$ with $|k|, |\ell| \geq 2n + r(n)$, there exists $z \in X$ such that $z|_{[-n,n]^2} = x|_{[-n,n]^2}$ and $(T^{-(k,\ell)}z)|_{[-n,n]^2} = y|_{[-n,n]^2}$. $X$ is strongly irreducible if you can take $r$ fixed, independent of $n$.

Questions about the mixing properties of proper $q$-colourings of $\mathbb{Z}^d$ are very rich. A lot of recent work has been done on this by Ron Peled, Yinon Spinka, Nishant Chandgotia, and their collaborators, though they focus more on measure-theoretic mixing notions.