Graph Powers of Groups

Abstract

The Lights Out Puzzle, played on a graph $\hat{I}“$, 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 \textit{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^{\hat{I}}“$. 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}}^{|\hat{I}“|}$. 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.

20 pages (16 pages of main text, 4 pages of appendices and bibliography), 3 figures, submitted to The Electronic Journal of Combinatorics