6
$\begingroup$

Let us call $G$ a graph with vertices in two possible colours. If we select a vertex, we change the colour of it and of every vertex that is adjacent to it. Is it possible to change a graph from all the first colour to all the second using such moves?

I cannot find any counter example but either cannot find a proof. What do you think?

$\endgroup$
5
  • 2
    $\begingroup$ When you say $G$ is "a graph with two coloured vertices", are you saying that just two of the vertices are coloured, or that every vertex is coloured with one of two colours? $\endgroup$ Commented Nov 1, 2018 at 10:13
  • 1
    $\begingroup$ There is a strategy to do it for each cycle graph by selecting each node once. Also, the order of selecting is not important for any graph. Maybe this is helpful? $\endgroup$ Commented Nov 1, 2018 at 10:32
  • 3
    $\begingroup$ It can be done for any graph. The general proof uses linear algebra. This is a famous problem, called the "lamp lighting problem" or the "lights out game" or the "all ones problem" and there is a lot of literature about it. For example this paper: arxiv.org/abs/math/0411201 $\endgroup$
    – bof
    Commented Nov 1, 2018 at 10:32
  • 1
    $\begingroup$ K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53. $\endgroup$
    – bof
    Commented Nov 1, 2018 at 10:36
  • $\begingroup$ thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color $\endgroup$ Commented Nov 1, 2018 at 12:21

2 Answers 2

5
$\begingroup$

The answer is YES and the above comments give several references for this result called the "lamp lighting problem". Below there is a direct proof.

Let $G$ be a graph with vertices $v_1,v_2,\dots, v_n$ and let $A$ be a matrix such that $a_{ij}=1$ if and only if $i=j$ or there is an edge between $v_i$ and $v_j$.

Assume that the vertices of $G$ are all blue (colour $0$). It is possible to change their colour to red (colour $1$) by using the those moves if and only if there is a vector $y=(y_1,\dots y_n)^t\in \mathbb{Z}_2^n$ such that $$Ay=u$$ where $u=(1,1,\dots,1)^t$, that is, since the matrix $A$ is symmetric, if and only if $$u\in \text{Im}(A)=\text{Im}(A^t)=(\text{Ker}(A))^{\perp}.$$ Thus it suffices to show that $Ax=0$ implies $u\cdot x=0$: $$\begin{align} 0&=\sum_{i=1}^n(Ax)_i=\sum_{i=1}^nx_i+\sum_{i=1}^n\sum_{j\not=i}a_{ij}x_j\\ &=u\cdot x+2\sum_{1\leq i<j\leq n}a_{ij}x_j= u\cdot x \pmod{2}. \end{align}$$ and we are done.

$\endgroup$
2
  • $\begingroup$ hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$\text{Im}(A^t)=(\text{Ker}(A))^{\perp}.$$ $\endgroup$ Commented Nov 1, 2018 at 12:16
  • 1
    $\begingroup$ Note that, $x\in \text{Ker}(A)$ iff $0=\langle Ax,y\rangle = \langle x, A^ty\rangle$ for all $y$. $\endgroup$
    – Robert Z
    Commented Nov 1, 2018 at 12:41
4
$\begingroup$

Yes, it can be done for any graph. This is a much-discussed problem called the "lamp lighter's problem" or the "all ones problem" or "lights out". This paper which is available online looks like a good survey:
Rudolf Fleischer and Jiajin Yu, A Survey of the Game "Lights Out".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .