# 2015 Workshop on Combinatorics and Applications at SJTU

April 21 -- 27, Shanghai Jiao Tong University

Date: Saturday, April 25, 2015

Time: 10:45 - 11:30

Venue: Large Meeting Room, Math Building

Title: The Lit-Only $\sigma$-Game

Abstract:

Let $G$ be a finite graph with vertex set $V$ which may not necessarily be loopless. For each $v \in V$, let $\alpha_v \in {\bf F}^V_2$ be the map which takes value $1$ on $w \in V$ if and only if there is an edge between $v$ and $w$ in $G$; let ${\cal T}_v$ be the linear map on ${\bf F}^V_2$ that sends $x \in {\bf F}^V_2$ to itself if $x(v) = 0$ and sends $x \in {\bf F}^V_2$ to $x + \alpha_v$ if $x(v) = 1$. We consider the digraph $\Gamma$ with vertex set ${\bf F}^V_2$ and arc set $\{ (x, {\cal T}_v(x) : x \in {\bf F}^V_2, v \in V\}$, which is the phase space of the lit-only $\sigma$-game on $G$.

We determine the reachability relation for the digraph $\Gamma$. A surprising corollary of this work is that, for $\alpha, \beta \in {\bf F}^V_2$, basically, $\alpha$ can reach $\beta$ in $\Gamma$ if and only if $\alpha - \beta$ lies in the binary linear subspace spanned by $\{ \alpha_v : v \in V\}$.

An important step of our work is to define the line graph of a multigraph and to provide a forbidden subgraph characterization of it.

This is joint work with Yaokun Wu.

Slides: View slides

Webmaster