Graph Powers of Groups

Abstract

The Lights Out Puzzle, played on a graph $\Gamma$, has been studied using linear algebra over $\mathbb{F}_2$ and more generally over $\mathbb{Z}/k\mathbb{Z}$. We generalize the setting by allowing the states of vertices to be the elements of a group $G$, where a 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^{\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}^{|\Gamma|}$. While most graphs appear to be RA, we show the odd-dimensional cube graphs $Q_{2n+1}$ and folded cube graphs $\square_d$, for $d$ odd or 2, are not.