Graph Powers of Groups

The Lights Out Puzzle, played on a graph $\mathrm{\Gamma }$, has been studied using linear algebra over ${\mathbb{F}}_2$ and more generally over $\mathbb{Z}\mathrm{/}k\mathbb{Z}$. We generalize the setting by allowing the states of vertices to be the elements of a group $G$, where a $\mathit{\text{click}}$ in vertex $v$ multiplies the state of $v$ and its neighbors by an element $g\in G$ on the right. Starting with the identity element $e\in G$ for all vertices, the totality of all achievable state configurations forms a group $G^{\mathrm{\Gamma }}$. This group generalizes parallel products of group actions and provides a rich structure for analysis. For many graphs, which we term ``RA’’ (reducible to abelian), the problem reduces – regardless of $G$ – to a linear algebra question over $\mathbb{Z}$. We discuss a chain of five different subgroups consisting of commutators and introduce techniques for showing that families of graphs are RA using each. In particular, using Heisenberg groups, we establish that a graph is RA precisely when a certain lattice spans ${\mathbb{Z}}^{\mathrm{\mid }\mathrm{\Gamma }\mathrm{\mid }}$. While most graphs appear to be RA, we show the odd-dimensional cube graphs $Q_{2n+1}$ and folded cube graphs ${\mathrm{\square }}_d$, for $d$ odd or 2, are not.