A Cayley Graph with Chromatic Number Three and No Invariant Random Three-Coloring

Abstract

We construct a connected seven-regular Cayley graph of (C5 * (C2 x C2)) x C2 with chromatic number three but no translation-invariant random proper three-coloring. A central involution partitions two finite subgroup graphs into pairs. Every proper three-coloring has at least four equal-colored pairs out of five in a blown-up five-cycle, and at most one out of four in a crown graph. Translation invariance would force the same probability to be at least 4/5 and at most 1/4. An explicit reduced-word rule gives a proper three-coloring of the entire graph, while a finite quotient supplies an invariant random four-coloring. Thus the invariant chromatic number is exactly four, giving a negative answer to the optimal invariant random coloring question of Lyons and Schramm, also recorded as Abért Question 31. Author: Alper Ferudun, Mercury Software GmbH. This English manuscript is an AI-assisted, self-audited and unrefereed preprint. The all-word proof is supplemented by an exact standard-library Python checker. No independent review, formal certification or absolute priority is claimed. Source record: AMR-011-0031 in ulamai/UnsolvedMath v1.6.0. Licensed under CC BY 4.0.