Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 77 posts

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#31

Post by avip »

glitcher wrote: post #22

> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…

>I’m not an expert on the four color problem, but I assume the proof is true. However, it’s not beautiful. I’d prefer to see a proof that gives insight into why four colors are sufficient.

P. Erdos

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#32

Post by pfdietz »

avip wrote: post #31
glitcher wrote: post #22

> Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, ... > Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering). I know very little about graphs and found this bit surprising. After some searching I found out it is called the Four Color Theorem. Does anyone know o…

>I’m not an expert on the four color problem, but I assume the proof is true. However, it’s not beautiful. I’d prefer to see a proof that gives insight into why four colors are sufficient. P. Erdos

The proof has been formalized and verified in the Coq theorem proving system, which is good evidence it is correct.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#33

Post by Twisol »

pfdietz wrote: post #32
avip wrote: post #31

Earlier quoted context omitted.

>I’m not an expert on the four color problem, but I assume the proof is true. However, it’s not beautiful. I’d prefer to see a proof that gives insight into why four colors are sufficient. P. Erdos

The proof has been formalized and verified in the Coq theorem proving system, which is good evidence it is correct.

That wasn't really Erdős' issue with the proof. Unsolved problems in mathematics are often not important merely because of other problems that depend on them; you can look at the Riemann hypothesis to see how much work has already been done just assuming its truth. We're interested in these problems because we hope that the proof will teach new tools and grant new insights, and possibly spark other problems and generalizations.

A proof that requires a computer to understand it is not helpful for these goals. The proof's veracity is not in question.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#35

Post by avip »

pfdietz wrote: post #32
avip wrote: post #31

Earlier quoted context omitted.

>I’m not an expert on the four color problem, but I assume the proof is true. However, it’s not beautiful. I’d prefer to see a proof that gives insight into why four colors are sufficient. P. Erdos

The proof has been formalized and verified in the Coq theorem proving system, which is good evidence it is correct.

Erdos did not live to see that (and it would have made no difference to his comment).

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#36

Post by 2bitencryption »

I'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 neighbors must be pidgeon-holed to share a color with the node? Are there constraints on how many neighbors a node can have?

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#37

Post by dnadler »

2bitencryption wrote: post #36

I'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…

In your example the middle node could be green, and the nodes it shares edges with could alternate between red, blue and yellow as you iterate over them.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#38

Post by kfichter »

2bitencryption wrote: post #36

I'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…

You could simply alternate colors around the node in that case:

  #%#
  %x%
  #%#

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#39

Post by andrelaszlo »

2bitencryption wrote: post #36

I'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…

"In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet."

https://en.wikipedia.org/wiki/Four_color_theorem

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#40

Post by 2bitencryption »

dnadler wrote: post #37
2bitencryption wrote: post #36

I'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…

In your example the middle node could be green, and the nodes it shares edges with could alternate between red, blue and yellow as you iterate over them.

it took me a moment, but now it seems obvious. Thanks :)
Post reply on HN