7 ms·
Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
- FabHK 7y agoBeautiful 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.)
- pmiller2 7y agoI’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).
- edjrage 7y agoThe text and the examples are good enough, but I'm sure just one example accompanied by some nice illustrations would be much more immediately illuminating.
- klyrs 7y agoBecause 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.
- FabHK 7y agoI 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).
- klyrs 7y agoMaybe to subtly discourage a misconception, that it's only about students x instruments? Kinda reaching here and I see what you mean
- zten 7y agoI don't think it's that big of a reach! I agree that it might be a bit unnecessary in this context, but in math classes it was always enormously valuable to have more examples than fewer ones. The pattern would become easier to identify. This helped out quite a bit if an example mixed in some other concept that I was quite a bit weaker at, because additional fully-worked examples would separate out all of the components and help me figure out what was blocking my full understanding of the problem.
- gpvos 7y agoWithout the examples, I wouldn't have understood the article. And I did have some graph theory way back in university.
- addicted 7y agoThe first example is used to explain what a tensor product of 2 graphs is. The second example was used to show how colouring the tensor product may actually be useful. I thought the second example was a little more complex (primarily because it requires the connection of incompatible nodes, as opposed to the more straightforward pairing of compatible nodes), so having a different, more straight forward example to just explain tensor products was helpful. Also, having 2 different unrelated examples for the same thing can definitely help with understanding the underlying property/theorem.
- pmiller2 7y agoThis 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.... :)
- avaku 7y agoHe commented (in the article) that he is delighted the resolution has been found and that "it can be explained in two sentences".
- pmiller2 7y agoI know. Otherwise, I would have said some variation of “big if true.” Or, maybe I would have emailed him about it. :)
- C4stor 7y agoThe construction can be explained in two sentences, the argument proving this is a proper counter example not exactly I think !
- _delirium 7y agoAlthough not that much more even for the proof... the paper is 2 1/2 pages, and almost half of that is introduction and references.
- _1 7y ago> (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.
- pmiller2 7y agoHe could probably do an entire course on just papers he wrote or co-wrote.
- firstinstinct 7y agoLong 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.
- pmiller2 7y agoWhat results and special cases did you work on?
- firstinstinct 7y agoI cannot remember. I emailed him about some results, he said they were interesting, but later I discovered those results were already published. I told him : I will throw them to trash. Very impolite from my part!, that must be 20 years ago.
- hammock 7y agoTangential: 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.
- b_tterc_p 7y agoProbably you would model it as a mixed integer optimization task, and optimize for max % competence across picked duets. 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.
- jes5199 7y agoyes: you're thinking of a "edge-weighted graph". And extending the tensor product to preserve probabilities is straightforward - you can just multiply the weights of each original pair of edges to get the weight of the edge in the tensor product graph.
- ky3 7y ago> how do you account for non-binary strength of connections between nodes The adjacency matrix of a graph normally has entries only 0 or 1. https://en.wikipedia.org/wiki/Adjacency_matrix https://en.wikipedia.org/wiki/Adjacency_matrix Generalize the adjacency matrices to include values between 0 and 1. Typically, you'd impose some normalization condition like rows and/or columns sum to 1. Then compute the Kronecker product of matrices to obtain the graph tensor product. https://en.wikipedia.org/wiki/Kronecker_product https://en.wikipedia.org/wiki/Kronecker_product
- glitcher 7y ago> 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 of a resource that provides a more intuitive explanation for this for non-graph-theorists?
- urmish 7y agoIntuitive explanation about the proof? That might be tricky because it took a computer to prove it.
- intuitionist 7y agoYou can get some way there with a proof of the five-color theorem, though, which is much simpler. There’s also a good popular overview of the history of the problem in the book “Four Colors Suffice” by Robin Wilson.
- hawkice 7y agoIt required a notoriously hard-to-simplify proof, which required computer assisted brute force analysis. But an intuition is that a complete graph with four nodes is planar, and five is not. A (3,3) bipartite graph is also the smallest non-planar bipartite graph. That's probably good for answering "why would you suspect 4".
- jessriedel 7y agoTo 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.
- rocqua 7y agoNotably one you can draw on either a flat piece of paper or a sphere. On a torus, you need up to 7 colors.
- urmish 7y agoLooks like this is the paper: COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE https://arxiv.org/pdf/1905.02167.pdf https://arxiv.org/pdf/1905.02167.pdf
- 2bitencryption 7y agoI'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?
- dnadler 7y agoIn 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.
- 2bitencryption 7y agoit took me a moment, but now it seems obvious. Thanks :)
- kfichter 7y agoYou could simply alternate colors around the node in that case: #%# %x% #%#
- andrelaszlo 7y ago"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 https://en.wikipedia.org/wiki/Four_color_theorem
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]
- MrXOR 7y agoMy 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-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/ https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-m... Congratulations to Yaroslav Shitov!
- dylanfw 7y agoCould 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?
- karmakaze 7y agoThe 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.
- dylanfw 7y agoThank 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.
- philipfweiss 7y agoFour 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).
- dylanfw 7y agoThank 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).
- Cogito 7y agoIs 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?
- OscarCunningham 7y agoThey'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-that-requires-5-colors-but-does-not-contain-k5-complete-graph-on-5-vertices/ https://standardwisdom.com/softwarejournal/2012/07/a-graph-t...
- Cogito 7y agoThanks, that's a really great example. It definitely feels non trivial to come up with an example.
- intuitionist 7y agoNo, 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.)
- Cogito 7y agoTo 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.
- thesz 7y agoFrom the article: "Now that mathematicians know Hedetniemi’s conjecture is false, the natural next question is just how false it is..." And from Stanislaw Lem works (Cyberiad): "Everyone knows that dragons don’t exist. But while this simplistic formulation may satisfy the layman, it does not suffice for the scientific mind." Time to read some Lem again?.. ;)