Dgdrxrt

What was the last x86 CPU that did not have the x87 floating-point unit built in?

TDS update packages don't remove unneeded items

How to read αἱμύλιος or when to aspirate

Why can I use a list index as an indexing variable in a for loop?

Is there a way to generate uniformly distributed points on a sphere from a fixed amount of random real numbers per point?

How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time

How to make Illustrator type tool selection automatically adapt with text length

What can I do if neighbor is blocking my solar panels intentionally?

What aspect of planet Earth must be changed to prevent the industrial revolution?

The following signatures were invalid: EXPKEYSIG 1397BC53640DB551

Button changing its text & action. Good or terrible?

Is this wall load bearing? Blueprints and photos attached

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

Does Parliament hold absolute power in the UK?

How do you keep chess fun when your opponent constantly beats you?

Is an up-to-date browser secure on an out-of-date OS?

Can I visit the Trinity College (Cambridge) library and see some of their rare books

Working through the single responsibility principle (SRP) in Python when calls are expensive

What to do when moving next to a bird sanctuary with a loosely-domesticated cat?

Circular reasoning in L'Hopital's rule

Am I ethically obligated to go into work on an off day if the reason is sudden?

Is every episode of "Where are my Pants?" identical?

What happens to a Warlock's expended Spell Slots when they gain a Level?

Would an alien lifeform be able to achieve space travel if lacking in vision?

Colored graph with $2$ colors

5

3

$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?

combinatorics graph-theory puzzle

share|cite|improve this question

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

$endgroup$

• 
  
  
  

  
  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$
  – Theo Bendit
  Nov 1 '18 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$
  – Wauzl
  Nov 1 '18 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
  Nov 1 '18 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
  Nov 1 '18 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$
  – Marine Galantin
  Nov 1 '18 at 12:21
  

  
  
  
  

add a comment | 

5

3

$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?

combinatorics graph-theory puzzle

share|cite|improve this question

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

$endgroup$

• 
  
  
  

  
  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$
  – Theo Bendit
  Nov 1 '18 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$
  – Wauzl
  Nov 1 '18 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
  Nov 1 '18 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
  Nov 1 '18 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$
  – Marine Galantin
  Nov 1 '18 at 12:21
  

  
  
  
  

add a comment | 

$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?

combinatorics graph-theory puzzle

share|cite|improve this question

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

$endgroup$

share|cite|improve this question

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

share|cite|improve this question

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

edited Mar 31 at 6:08

Eric Wofsey

193k14220352

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

asked Nov 1 '18 at 10:05

Marine GalantinMarine Galantin

977419

2 Answers
2

active

oldest

votes

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)^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.

share|cite|improve this answer

edited Nov 1 '18 at 12:11

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
  $endgroup$
  – Marine Galantin
  Nov 1 '18 at 12:16
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
  $endgroup$
  – Robert Z
  Nov 1 '18 at 12:41
  
  

  
  
  
  

add a comment | 

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".

share|cite|improve this answer

answered Nov 1 '18 at 11:49

bofbof

52.6k559121

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

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

Name

Email

Required, but never shown

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)^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.

share|cite|improve this answer

edited Nov 1 '18 at 12:11

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
  $endgroup$
  – Marine Galantin
  Nov 1 '18 at 12:16
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
  $endgroup$
  – Robert Z
  Nov 1 '18 at 12:41
  
  

  
  
  
  

add a comment | 

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)^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.

share|cite|improve this answer

edited Nov 1 '18 at 12:11

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  hi, thank you for your answer. May I ask, what is the argument that justify the equality ? $$textIm(A^t)=(textKer(A))^perp.$$
  $endgroup$
  – Marine Galantin
  Nov 1 '18 at 12:16
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Note that, $xin textKer(A)$ iff $0=langle Ax,yrangle = langle x, A^tyrangle$ for all $y$.
  $endgroup$
  – Robert Z
  Nov 1 '18 at 12:41
  
  

  
  
  
  

add a comment | 

$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)^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.

share|cite|improve this answer

edited Nov 1 '18 at 12:11

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

$endgroup$

share|cite|improve this answer

edited Nov 1 '18 at 12:11

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

answered Nov 1 '18 at 10:23

Robert ZRobert Z

102k1072145

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".

share|cite|improve this answer

answered Nov 1 '18 at 11:49

bofbof

52.6k559121

$endgroup$

add a comment | 

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".

share|cite|improve this answer

answered Nov 1 '18 at 11:49

bofbof

52.6k559121

$endgroup$

add a comment | 

$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".

share|cite|improve this answer

answered Nov 1 '18 at 11:49

bofbof

52.6k559121

$endgroup$

share|cite|improve this answer

answered Nov 1 '18 at 11:49

bofbof

52.6k559121

answered Nov 1 '18 at 11:49

bofbof

52.6k559121

answered Nov 1 '18 at 11:49

bofbof

52.6k559121