Note on the lamp lighting problem

DOI10.1006/AAMA.2001.0739MaRDI QIDQ5956771zbMATH OpenOpenAlexFDO

Authors Henrik Eriksson, Kimmo Eriksson, Jonas Sjöstrand

Publication date 16 June 2002

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0411201

zbMATH Keywords

tilingsmatchingslamp lighting

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrices, determinants in number theory (11C20) Matrices of integers (15B36) Combinatorial aspects of tessellation and tiling problems (05B45) Cellular automata (computational aspects) (68Q80) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Abstract: We answer some questions concerning the so called sigma-game of Sutner. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lamp. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the special case of an orthogonal grid one gets a criterion for whether the number of monomer-dimer tilings of an m times n grid is odd or even.

Recommendations

• scientific article; zbMATH DE number 700992
• scientific article; zbMATH DE number 67624
• The Floodlight Problem
• Revisiting Lambert's problem
• A counterexample to the lights out problem
• On the solution to every Lambert problem

Cites work

• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• Characterizing switch-setting problems^∗
• Linear cellular automata and the garden-of-eden
• Merlin's Magic Square
• Merlin's Magic Square Revisited
• The σ-Game and Cellular Automata
• \(\sigma\)-Automata and Chebyshev-polynomials
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata

Cited in

(19)

• Chasing the lights in Lights Out
• Solutions to all-colors problem on graph cellular automata
• Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
• Construction of \(\sigma^+\)-game solutions on a rectangular grid
• Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs
• Lit-only \(\sigma \)-game on pseudo-trees
• Effects of edge addition or removal on the nullity of a graph
• Lit-only sigma game on a line graph
• The edge-flipping group of a graph
• Minimum light number of lit-only \(\sigma\)-game on a tree
• Maximum orbit weights in the -game and lit-only -game on grids and graphs
• Lights Out On A Random Graph
• A Survey of the Game “Lights Out!”
• Completely symmetric configurations for \(\sigma \)-games on grid graphs
• ``Lights Out and variants
• Universal configurations in light-flipping games
• On the complexity of dominating set problems related to the minimum all-ones problem
• Generalized switch-setting problems
• The general \(\sigma \) all-ones problem for trees

This page was built for publication: Note on the lamp lighting problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956771)