1
$\begingroup$

Suppose there is an undirected graph $G=(V,E)$. Each node $v\in V$ is allowed to be labelled either "$0$" or "$1$". Define an "operation" $f_v$ for each $v\in V$ which toggles the label for $v$ and all $v$'s neighbours (i.e. all the other $v'\in V$ such that $v'$ is connected to $v$ via some edge $e'\in E$) to the opposite label. Initially, each node is labelled "$0$".

Question: Prove or disprove that we can toggle all labels to "$1$" only by performing the operations $\{f_v\mid v\in V\}$.

Sorry, I have no idea where to start since I'm not familiar with graphs at all... I don't even know whether the statement is true or false. Could somebody kindly tell me how to prove/disprove it or at least where to look? Thanks.


EDIT As pointed out in comments, not a counter-example: first toggle the top and bottom nodes in the first column, and then the single node in the third column.

Failed attempt: Not sure if the following furnishes a counter-example but here it goes:

enter image description here


Background This question came from a friend of mine who was inspired when he was having a Chinese family dinner. In such family dinners, a very pronounced type of activities is "propose toasts" i.e. one will toast to his families for good fortune etc and then this person and all the people he toasts to will drink up their wine ("bottom up") and then refill for the next round of toasting. So now let's imagine a huge Chinese dinner with lots of people and some know each other but others don't. And let's suppose additionally:

1). If somebody is gonna propose a toast, they toast simultaneously to everybody they know but not to those they don't know. (By the way, "knowing" is a reciprocal relation here, A knows B if and only if B knows A.)

2). There are two types of wine: beers and Chinese spirits. And when one drinks up their current glass, they will refill it with the other (alternating) type of wine.

Initially everybody has their glass filled with Chinese spirits. Is it possible that everybody ends up with beers in their glass?

$\endgroup$
5
  • 1
    $\begingroup$ This has been implemented as a puzzle game, called Lights Out. On any graph it is always possible to go from the all-0 state to the all-1 state (or vice versa). $\endgroup$ Commented Feb 4, 2019 at 15:56
  • $\begingroup$ @JaapScherphuis thanks could you kindly provide a reference to the claim that Lights Out is solvable on any graph to go from all 1s to all 0s? $\endgroup$
    – Vim
    Commented Feb 4, 2019 at 16:07
  • $\begingroup$ You can take a look at my Lights Out Maths page, or look at Note on the lamp lighting problem by Eriksson et al, or one of the first papers about this, the 1989 Linear cellular automata and the garden-of-eden by Klaus Sutner. $\endgroup$ Commented Feb 4, 2019 at 16:26
  • $\begingroup$ @JaapScherphuis thanks for these resources. I'll check it out. Could you please also look at my "counter-example" (new edit)? I kind of feel there's no way to do that one... $\endgroup$
    – Vim
    Commented Feb 4, 2019 at 16:32
  • 3
    $\begingroup$ In your graph, you can toggle the top and bottom nodes in the first column, and then the single node in the third column. $\endgroup$ Commented Feb 4, 2019 at 16:33

2 Answers 2

2
$\begingroup$

The statement is true. The Garden-of-Eden paper of Sutner studies the problem using cellular automata.

Here is another shot using linear algebra. First, notice that if you perform the operations $f_{v_1}, \dotsc, f_{v_k}$, the order on which these operations are performed does not matter, they all give the same output. Next, performing the same operation $f_v$ twice cancels itself. Thus it is enough to find $S \subseteq V(G)$ and perform $\{ f_v : v \in S \}$.

We might phrase this problem as a system of linear equations in $\mathbf{F}_2$, the field with two elements. Let $A$ be the adjacency matrix of the graph $G$ and let $I$ be the identity matrix whose rows and columns are indexed by $V(G)$. If $S \subseteq V(G)$, let $\chi_S$ be the (column) $\{0,1\}$-vector indexed by $V(G)$ with an $1$ in the coordinate $v$ if and only if $v \in S$. Then the problem is equivalent to solving the system $(A + I)\chi_S = 1$ over $\mathbf{F}_2$, where $1$ is the all-ones vector. To solve the problem then it is enough to see that $1$ is in the range of the matrix $(A+I)$. That is exactly the approach taken here, and the proof is very simple.

$\endgroup$
0
$\begingroup$

The statement do not seem to true in general, well you may add another condition of connected graph without any cycle to check whether the statement is true or not

I think I have found a counter example for the general case ,

Consider a graph with a three cycle , two of whose vertex (name them as A) has degree two and the the third one may have degree >=2. Say we have initially opposite number assigned to them (A vertices), now it seems from here we cannot make the A vertices have same number because toggling any vertex preserves the opposite number assigned to A vertices.

$\endgroup$
5
  • $\begingroup$ @DavidHackenger Can you please give me the mistake in the reasoning , for the statement to be wrong for the case where the graph can have cycle? I am not arguing but still want to know my mistake, hope you would help. $\endgroup$ Commented Feb 4, 2019 at 17:29
  • $\begingroup$ Turn on all the neighbors of degree 3 vertex $\endgroup$
    – dEmigOd
    Commented Feb 5, 2019 at 8:43
  • $\begingroup$ Can you please explain? $\endgroup$ Commented Feb 5, 2019 at 11:06
  • $\begingroup$ Like this drive.google.com/file/d/10DTeQMFfezc4DxHBAeCXI3cAX34q1XVy/… $\endgroup$
    – dEmigOd
    Commented Feb 5, 2019 at 12:51
  • $\begingroup$ Sorry for the trouble understood , the trivial way of making all 1 in my given graph. $\endgroup$ Commented Feb 5, 2019 at 13:56

You must log in to answer this question.

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