Mixing
Colored graph with 2 colors
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Let us call G a graph with vertices in two possible colours. If we select a vertex, we change the color of it and of every vertex that is adjacent to it. Is it possible to change a graph from all the first color to all the second using such moves?
I cannot find any counter example but either cannot find a proof. What do you think?
problem-solving puzzle
edited 2 hours ago
Parcly Taxel
38.9k137097
asked 3 hours ago
Marine Galantin
612112
add a comment |Â
up vote
4
down vote
favorite
Let us call G a graph with vertices in two possible colours. If we select a vertex, we change the color of it and of every vertex that is adjacent to it. Is it possible to change a graph from all the first color to all the second using such moves?
I cannot find any counter example but either cannot find a proof. What do you think?
problem-solving puzzle
edited 2 hours ago
Parcly Taxel
38.9k137097
asked 3 hours ago
Marine Galantin
612112
2
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?
– Theo Bendit
2 hours ago
1
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?
– Wauzl
2 hours ago
3
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
– bof
2 hours ago
1
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
2 hours ago
thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color
– Marine Galantin
45 mins ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Let us call G a graph with vertices in two possible colours. If we select a vertex, we change the color of it and of every vertex that is adjacent to it. Is it possible to change a graph from all the first color to all the second using such moves?
I cannot find any counter example but either cannot find a proof. What do you think?
problem-solving puzzle
edited 2 hours ago
Parcly Taxel
38.9k137097
asked 3 hours ago
Marine Galantin
612112
Let us call G a graph with vertices in two possible colours. If we select a vertex, we change the color of it and of every vertex that is adjacent to it. Is it possible to change a graph from all the first color to all the second using such moves?
I cannot find any counter example but either cannot find a proof. What do you think?
problem-solving puzzle
problem-solving puzzle
edited 2 hours ago
Parcly Taxel
38.9k137097
asked 3 hours ago
Marine Galantin
612112
edited 2 hours ago
Parcly Taxel
38.9k137097
asked 3 hours ago
Marine Galantin
612112
edited 2 hours ago
Parcly Taxel
38.9k137097
edited 2 hours ago
Parcly Taxel
38.9k137097
edited 2 hours ago
Parcly Taxel
38.9k137097
38.9k137097
asked 3 hours ago
Marine Galantin
612112
asked 3 hours ago
Marine Galantin
612112
asked 3 hours ago
Marine Galantin
612112
612112
2
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?
– Theo Bendit
2 hours ago
1
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?
– Wauzl
2 hours ago
3
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
– bof
2 hours ago
1
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
2 hours ago
thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color
– Marine Galantin
45 mins ago
add a comment |Â
2
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?
– Theo Bendit
2 hours ago
1
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?
– Wauzl
2 hours ago
3
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
– bof
2 hours ago
1
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
2 hours ago
thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color
– Marine Galantin
45 mins ago
2
2
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?
– Theo Bendit
2 hours ago
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?
– Theo Bendit
2 hours ago
1
1
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?
– Wauzl
2 hours ago
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?
– Wauzl
2 hours ago
3
3
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
– bof
2 hours ago
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
– bof
2 hours ago
1
1
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
2 hours ago
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
2 hours ago
thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color
– Marine Galantin
45 mins ago
thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color
– Marine Galantin
45 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
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)^tin mathbbZ_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
$$uin textIm(A)=textIm(A^t)=(textKer(A))^perp.$$
Thus it suffices to show that $Ax=0$ implies $ucdot x=0$:
$$beginalign
0&=sum_i=1^n(Ax)_i=sum_i=1^nx_i+sum_i=1^nsum_jnot=ia_ijx_j\
&=ucdot x+2sum_1leq i<jleq na_ijx_j= ucdot x pmod2.
endalign$$
and we are done.
answered 2 hours ago
Robert Z
87.9k1056127
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
add a comment |Â
up vote
3
down vote
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".
answered 1 hour ago
bof
48k449114
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
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)^tin mathbbZ_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
$$uin textIm(A)=textIm(A^t)=(textKer(A))^perp.$$
Thus it suffices to show that $Ax=0$ implies $ucdot x=0$:
$$beginalign
0&=sum_i=1^n(Ax)_i=sum_i=1^nx_i+sum_i=1^nsum_jnot=ia_ijx_j\
&=ucdot x+2sum_1leq i<jleq na_ijx_j= ucdot x pmod2.
endalign$$
and we are done.
answered 2 hours ago
Robert Z
87.9k1056127
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
add a comment |Â
up vote
3
down vote
accepted
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)^tin mathbbZ_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
$$uin textIm(A)=textIm(A^t)=(textKer(A))^perp.$$
Thus it suffices to show that $Ax=0$ implies $ucdot x=0$:
$$beginalign
0&=sum_i=1^n(Ax)_i=sum_i=1^nx_i+sum_i=1^nsum_jnot=ia_ijx_j\
&=ucdot x+2sum_1leq i<jleq na_ijx_j= ucdot x pmod2.
endalign$$
and we are done.
answered 2 hours ago
Robert Z
87.9k1056127
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
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)^tin mathbbZ_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
$$uin textIm(A)=textIm(A^t)=(textKer(A))^perp.$$
Thus it suffices to show that $Ax=0$ implies $ucdot x=0$:
$$beginalign
0&=sum_i=1^n(Ax)_i=sum_i=1^nx_i+sum_i=1^nsum_jnot=ia_ijx_j\
&=ucdot x+2sum_1leq i<jleq na_ijx_j= ucdot x pmod2.
endalign$$
and we are done.
answered 2 hours ago
Robert Z
87.9k1056127
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)^tin mathbbZ_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
$$uin textIm(A)=textIm(A^t)=(textKer(A))^perp.$$
Thus it suffices to show that $Ax=0$ implies $ucdot x=0$:
$$beginalign
0&=sum_i=1^n(Ax)_i=sum_i=1^nx_i+sum_i=1^nsum_jnot=ia_ijx_j\
&=ucdot x+2sum_1leq i<jleq na_ijx_j= ucdot x pmod2.
endalign$$
and we are done.
answered 2 hours ago
Robert Z
87.9k1056127
edited 56 mins ago
answered 2 hours ago
Robert Z
87.9k1056127
answered 2 hours ago
Robert Z
87.9k1056127
answered 2 hours ago
Robert Z
87.9k1056127
87.9k1056127
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
add a comment |Â
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
– Marine Galantin
50 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
– Robert Z
26 mins ago
add a comment |Â
up vote
3
down vote
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".
answered 1 hour ago
bof
48k449114
add a comment |Â
up vote
3
down vote
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".
answered 1 hour ago
bof
48k449114
add a comment |Â
up vote
3
down vote
up vote
3
down vote
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".
answered 1 hour ago
bof
48k449114
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".
answered 1 hour ago
bof
48k449114
answered 1 hour ago
bof
48k449114
answered 1 hour ago
bof
48k449114
answered 1 hour ago
bof
48k449114
48k449114
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2980219%2fcolored-graph-with-2-colors%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
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?
– Theo Bendit
2 hours ago
1
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?
– Wauzl
2 hours ago
3
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
– bof
2 hours ago
1
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), no. 2, 49–53.
– bof
2 hours ago
thank you all for your enlightning answers :) and my question was about that all the vertices can take either one or the other color
– Marine Galantin
45 mins ago