Note on the lamp lighting problem

Simple item page
dc.creatorEriksson, Henrik
dc.creatorEriksson, Kimmo
dc.creatorSjostrand, Jonas
dc.date2004-11-09
dc.date.accessioned2026-07-07T05:14:08Z
dc.date.available2026-07-07T05:14:08Z
dc.descriptionWe 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.
dc.description10 pages
dc.identifierhttps://arxiv.org/abs/math/0411201
dc.identifierhttp://arxiv.org/abs/math/0411201
dc.identifierAdvances of Applied Mathematics 27, 2001, pages 357-366
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/73163
dc.subjectCombinatorics
dc.subject05C50; 05B45, 52C20, 11C20, 15A36, 68Q80
dc.titleNote on the lamp lighting problem
dc.typetext

Files

Collections

arXiv