My lesson for today:
"Sometimes, the reason that a conjecture is very hard to prove is simply that it is false."
Worth to see:
https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-m...
Congratulations to Yaroslav Shitov!
Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
51–60 of 77 posts
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#52Earlier quoted context omitted.
To save laymen a google: A complete graph is one where all the nodes are connected. A planar graph is one that can be draw in the plane without two lines intersecting.
Notably one you can draw on either a flat piece of paper or a sphere. On a torus, you need up to 7 colors.
Yeah, any graph of a sphere can be easily deformed to fit on a plane, with something like stereographic projection
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#53Earlier quoted context omitted.
To save laymen a google: A complete graph is one where all the nodes are connected. A planar graph is one that can be draw in the plane without two lines intersecting.
Notably one you can draw on either a flat piece of paper or a sphere. On a torus, you need up to 7 colors.
Yep, and the proof that any graph that can be drawn without crossings on the torus can be properly colored with no more than 7 colors is vastly easier than the case for graphs drawn on the sphere/plane.
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#54Could somebody clear up my confusion with these two statements that appear contradictory?
"Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering)."
and
"Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G"
How can it be that 4 colors is sufficient for any graph, but for our hypothetical graph G we can't be sure that 5 colors are sufficient?
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#55Could somebody clear up my confusion with these two statements that appear contradictory? "Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering)." and "Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G"…
The map coloring problem relates to graphs that are planar--can be drawn on a 2D surface without crossing edges. Graphs in general are not planar and so more than 4 colors may be necessary.
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#56Could somebody clear up my confusion with these two statements that appear contradictory? "Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering)." and "Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G"…
Four colors is sufficient for a planar graph, but insufficient for a general graph. A planar graph is any graph where the edges can be drawn in such a way that they only intersect at the endpoints (there is a more formal algebraic definition but that helps with the intuition).
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#57I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing? > Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the ne…
[deleted]
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#58Could somebody clear up my confusion with these two statements that appear contradictory? "Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering)." and "Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G"…
The map coloring problem relates to graphs that are planar--can be drawn on a 2D surface without crossing edges. Graphs in general are not planar and so more than 4 colors may be necessary.
Thank you! That makes complete sense when I consider the 4 color example of a world map. I didn't even consider that most graphs would have "overlapping borders" on such a map.
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#59Could somebody clear up my confusion with these two statements that appear contradictory? "Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering)." and "Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G"…
Four colors is sufficient for a planar graph, but insufficient for a general graph. A planar graph is any graph where the edges can be drawn in such a way that they only intersect at the endpoints (there is a more formal algebraic definition but that helps with the intuition).
Thank you! That makes complete sense when I consider the 4 color example of a world map. I didn't even consider that most graphs would have "overlapping borders" on such a map.
An extra thank you for apparently creating a new account to assist me. (I think that's what the green username indicates, at least).
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#60Is it true to say that a graph can be coloured by k colours if and only if the largest fully connected subgraph has k or fewer members?
For example, is saying a planar graph can always be coloured by 4 colours the same as saying a planar graph can never have more than 4 nodes that are all connected to each other?