11–20 of 77 posts
This 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".
Beautiful 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.)
Earlier quoted context omitted.
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).
Is there a way to include probability/fuzz into the tensor products? In other words, how do you account for non-binary strength of connections between nodes? Like I'm 80% good at piano but 50% good at oboe.
Earlier quoted context omitted.
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).
Maybe to subtly discourage a misconception, that it's only about students x instruments? Kinda reaching here and I see what you mean
Tangential: I don't know anything about graph theory but I'm intrigued by the student-instrument duet example. Is there a way to include probability/fuzz into the tensor products? In other words, how do you account for non-binary strength of connections between nodes? Like I'm 80% good at piano but 50% good at oboe.
Not terribly dissimilar from a traveling salesman problem where you pick the order of nodes traveled between to minimize distance.
Note that the graph coloring described here is a way of defining what the possible nodes and edges are in the duet example. You still need to do some sort of solving on to find a feasible solution within the graph, which would likely also involve the same logic I mentioned above.
Tangential: I don't know anything about graph theory but I'm intrigued by the student-instrument duet example. Is there a way to include probability/fuzz into the tensor products? In other words, how do you account for non-binary strength of connections between nodes? Like I'm 80% good at piano but 50% good at oboe.
This 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.... :)
and apparently humble, too. I had one undergrad and one graduate class from him and didn't know about this.
This 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.... :)
> (also a great guy, to boot) and apparently humble, too. I had one undergrad and one graduate class from him and didn't know about this.
Beautiful 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).