2025/02/08 by Gabe Cunningham, Cunningham, Gabe, Igor Minevich +1 · 1 citation
Computer Science · Mathematics · #05C30 (Secondary) #20-02 (Primary) 20-04 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR)
paper · pdf · doi:10.48550/arxiv.2502.05648
openalex publication_date 2025/02/08 · openalex created_date 2025/02/12 · openalex updated_date 2026/07/28
The Lights Out Puzzle, played on a graph Γ, has been studied using linear algebra over \mathbbF2 and more generally over ℤ/kℤ. 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 ℤ. 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 ℤ|Γ|. While most graphs appear to be RA, we show the odd-dimensional cube graphs Q2n+1 and folded cube graphs \squared, for d odd or 2, are not.