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

61–70 of 77 posts

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#61

Post by pfdietz »

Twisol wrote: post #33
pfdietz wrote: post #32

Earlier quoted context omitted.

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 gener…

I was responding to the "I assume the proof is true". There's really no reason to just assume that.

Of course he's right that the proof was lacking in insight for human mathematicians. That's particularly important in combinatorics, which more than other areas of math grows by the accumulation of techniques rather than accumulation of results.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#62

Post by OscarCunningham »

Cogito wrote: post #60

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

They're not quite the same. Certainly if there are five vertices all connected to each other then the graph can't be four-coloured. But the converse isn't true.

https://standardwisdom.com/softwarejournal/2012/07/a-graph-t...

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#63

Post by kccqzy »

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…

The four color theorem is notoriously difficult to prove. However for intuitive understanding, you can look at the proof that five colors suffice to color any map. That proof should be understandable by anyone with an undergraduate level understanding of graph theory.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#64

Post by intuitionist »

Cogito wrote: post #60

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

No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t contain a complete subgraph on 5 vertices. But this isn’t sufficient to prove the four-color theorem.

There is a slight modification of the statement that may be correct; if you replace the condition of having a complete subgraph with that of having a complete minor, this is a very famous open problem called the Hadwiger conjecture. (It’s known to be true for the case n=5, i.e. every 5-chromatic graph has a K_5 minor.)

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#65

Post by Cogito »

intuitionist wrote: post #64
Cogito wrote: post #60

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

No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t contain a complete subgraph on 5 vertices. But this isn’t sufficient to prove the four-color theorem. There is a slight modification of the statement that may be correct; if you replace the condition of having a complete subgraph with that of having a complete mi…

To confirm I understand (and I think this is where I was at originally):

If a graph contains K_5 then it requires at least 5 colours to colour, but if a graph does not contain K_5 then it might still require 5 colours.

The example given by OscarCunningham is a great one.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#66

Post by intuitionist »

Cogito wrote: post #65
intuitionist wrote: post #64

Earlier quoted context omitted.

No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t contain a complete subgraph on 5 vertices. But this isn’t sufficient to prove the four-color theorem. There is a slight modification of the statement that may be correct; if you replace the condition of having a complete subgraph with that of having a complete mi…

To confirm I understand (and I think this is where I was at originally): If a graph contains K_5 then it requires at least 5 colours to colour, but if a graph does not contain K_5 then it might still require 5 colours. The example given by OscarCunningham is a great one.

Right—as mathematicians say, having a K_n subgraph is a sufficient but not necessary condition for having a chromatic number of at least n. Hadwiger’s conjecture goes the other way, stating that having a K_n minor is a necessary but not sufficient condition for having a chromatic number of at least n.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#67

Post by Cogito »

OscarCunningham wrote: post #62
Cogito wrote: post #60

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

They're not quite the same. Certainly if there are five vertices all connected to each other then the graph can't be four-coloured. But the converse isn't true. https://standardwisdom.com/softwarejournal/2012/07/a-graph-t...

Thanks, that's a really great example. It definitely feels non trivial to come up with an example.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#68

Post by emptybits »

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…

In addition to the excellent Numberphile video suggested, I enjoyed this book quite a bit although it took me a while to get through. (I'm interested in graph theory but it's not my background or strength.) Includes plenty of math and illustrations and the human side of this solution's history.

"Four Colors Suffice" by Robin Wilson

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#69

Post by anyfoo »

pfdietz wrote: post #61
Twisol wrote: post #33

Earlier quoted context omitted.

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 gener…

I was responding to the "I assume the proof is true". There's really no reason to just assume that. Of course he's right that the proof was lacking in insight for human mathematicians. That's particularly important in combinatorics, which more than other areas of math grows by the accumulation of techniques rather than accumulation of results.

And yet you assume that the problem was correctly stated in Coq, that the authors were using the software correctly, that they ran it more than once to account for random bit flips, that the authors are not just simply lying... while all those assumptions are reasonable, Erdös’s statement was as well.

Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

#70

Post by _delirium »

C4stor wrote: post #11
avaku wrote: post #8

Earlier quoted context omitted.

He commented (in the article) that he is delighted the resolution has been found and that "it can be explained in two sentences".

The construction can be explained in two sentences, the argument proving this is a proper counter example not exactly I think !

Although not that much more even for the proof... the paper is 2 1/2 pages, and almost half of that is introduction and references.
Post reply on HN