Graph Powers of Groups

The Lights Out Puzzle, played on a graph Γ, has been studied using linear algebra over F₂ and more generally over Z/kZ. 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 ∈ G on the right. Starting with the identity element e ∈ G for all vertices, the totality of all achievable state configurations forms a group GΓ. 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 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 Z|Γ|. While most graphs appear to be RA, we show the odd-dimensional cube graphs Q₂ₙ₊₁ and folded cube graphs d, for d odd or 2, are not.