Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
quantamagazine.org
Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
1–10 of 77 posts
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#2Beautiful article, though not sure why two examples are introduced (students x instruments, and jobs x hobbies).
The abstract for Shitov's paper is also a gem of brevity, here reproduced in its entirety:
"The chromatic number of G×H can be smaller than the minimum of the chromatic numbers of finite simple graphs G and H."
(And, of course, the first reference in the paper is co-authored by Erdős.)
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#3This is absolutely huge. Steve Hetdetniemi is one of the giants of the field (also a great guy, to boot). If he agrees the result is true, I believe it. Now, off to read the paper.... :)
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#4Beautiful article, though not sure why two examples are introduced (students x instruments, and jobs x hobbies). The abstract for Shitov's paper is also a gem of brevity, here reproduced in its entirety: "The chromatic number of G×H can be smaller than the minimum of the chromatic numbers of finite simple graphs G and H." (And, of course, the first reference in the paper is co-authored by Erdős.)
I’ll take 2 excellent examples over a definition and one opaque and unmotivated example any day (which is what you get in a lot of papers).
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#5Beautiful article, though not sure why two examples are introduced (students x instruments, and jobs x hobbies). The abstract for Shitov's paper is also a gem of brevity, here reproduced in its entirety: "The chromatic number of G×H can be smaller than the minimum of the chromatic numbers of finite simple graphs G and H." (And, of course, the first reference in the paper is co-authored by Erdős.)
Because it's an article for non-graph-theorists. People tend to follow sentences involving familiar categories, than "nodes of H" and "nodes of G".
And speaking as a graph theorist. When you've got three graphs like this, and you want to unambiguously refer to nodes of each, leaving things perfectly general can get quite tedious and torture the language. For example, sometimes it's just nicer to just say "red nodes" and "blue nodes" where any colors would suffice.
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#6Beautiful article, though not sure why two examples are introduced (students x instruments, and jobs x hobbies). The abstract for Shitov's paper is also a gem of brevity, here reproduced in its entirety: "The chromatic number of G×H can be smaller than the minimum of the chromatic numbers of finite simple graphs G and H." (And, of course, the first reference in the paper is co-authored by Erdős.)
Because it's an article for non-graph-theorists. People tend to follow sentences involving familiar categories, than "nodes of H" and "nodes of G". And speaking as a graph theorist. When you've got three graphs like this, and you want to unambiguously refer to nodes of each, leaving things perfectly general can get quite tedious and torture the language. For example, sometimes it's just nicer to just say "red nodes"…
I should clarify that I didn't wonder why an example was introduced (which makes perfect sense), but why more than one was introduced (not sure that makes sense for this type of overview article).
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#7Long time ago I failed to solve this conjecture. Nice to see it have been solved. I shared some email with S. Hetdetniemi about some special cases. Good old times.
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#8This is absolutely huge. Steve Hetdetniemi is one of the giants of the field (also a great guy, to boot). If he agrees the result is true, I believe it. Now, off to read the paper.... :)
He commented (in the article) that he is delighted the resolution has been found and that "it can be explained in two sentences".
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#9Long time ago I failed to solve this conjecture. Nice to see it have been solved. I shared some email with S. Hetdetniemi about some special cases. Good old times.
What results and special cases did you work on?
Re: Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
#10This is absolutely huge. Steve Hetdetniemi is one of the giants of the field (also a great guy, to boot). If he agrees the result is true, I believe it. Now, off to read the paper.... :)
He commented (in the article) that he is delighted the resolution has been found and that "it can be explained in two sentences".
I know. Otherwise, I would have said some variation of “big if true.” Or, maybe I would have emailed him about it. :)