Mathematician Disproves Hedetniemi’s Graph Theory Conjecture(quantamagazine.org)
quantamagazine.org
Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/
76 comments
The 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.
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.
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).
The 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.
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.
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.
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
I 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.
Without the examples, I wouldn't have understood the article. And I did have some graph theory way back in university.
My 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-m...
Congratulations to Yaroslav Shitov!
"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-m...
Congratulations to Yaroslav Shitov!
> 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?
> 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?
It 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".
To 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.
Notably one you can draw on either a flat piece of paper or a sphere. On a torus, you need up to 7 colors.
Yep, and the proof that any graph that can be drawn without crossings on the torus can be properly colored with no more than 7 colors is vastly easier than the case for graphs drawn on the sphere/plane.
Yeah, any graph of a sphere can be easily deformed to fit on a plane, with something like stereographic projection
Numberphile covered it well:
https://www.youtube.com/watch?v=NgbK43jB4rQ
It's also got a lot of videos on other cool math stuff.
It's also got a lot of videos on other cool math stuff.
>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
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.
A proof that requires a computer to understand it is not helpful for these goals. The proof's veracity is not in question.
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.
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.
Proving the theorem in a theorem proving engine adds credibility to the result, just like reproducing an experiment in science adds credibility to the experimental outcome.
The random bit flip comment is of course silly, since anyone can mechanically verify the Coq proof; it doesn't have to be those who created the proof. What has to be assumed is the correctness of the Coq kernel, but all uses of Coq contribute to that, not just this use.
The random bit flip comment is of course silly, since anyone can mechanically verify the Coq proof; it doesn't have to be those who created the proof. What has to be assumed is the correctness of the Coq kernel, but all uses of Coq contribute to that, not just this use.
I have no idea what you are even arguing anymore. I made the "bit flip" comment specifically to show that even with the most credible proof, there are still always at least some little (and possibly completely trivial) implicit assumptions made about the actual correctness of the proof. One of those trivial assumptions is that the authors ran their code enough (most likely just as part of just writing it and getting it ready for publishing) more than once. Or that anyone else did, as you say.
And so I simply don't get why you're so hung up on Erdős's assumption of credible mathematicians making a credible proof. Are you seriously insinuating that Paul Erdős, of all people, was not aware of everything you're saying here?
And so I simply don't get why you're so hung up on Erdős's assumption of credible mathematicians making a credible proof. Are you seriously insinuating that Paul Erdős, of all people, was not aware of everything you're saying here?
> even with the most credible proof, there are still always at least some little (and possibly completely trivial) implicit assumptions made about the actual correctness of the proof
This is true of any proof, not only computerised proofs. Sometimes maths journals publish incorrect proofs because a person made a mistake. I doubt an incorrect proof has ever been published on account of a hardware bit-flip.
I'd be more worried about the kind of deterministic failure than manifests in every run, such as a bug in the CPU (the famous Intel floating-point bug, say), or in the operating system, etc. Could be mitigated by using a variety of platforms I suppose.
This is true of any proof, not only computerised proofs. Sometimes maths journals publish incorrect proofs because a person made a mistake. I doubt an incorrect proof has ever been published on account of a hardware bit-flip.
I'd be more worried about the kind of deterministic failure than manifests in every run, such as a bug in the CPU (the famous Intel floating-point bug, say), or in the operating system, etc. Could be mitigated by using a variety of platforms I suppose.
And the silly hardware bit flip complaint is easily addressed: run the program N times, and reduce the chance of the error by a factor that's exponential in N.
Large randomly generated primes are produced by a random algorithm like this, with a step that (when run on a composite number) shows that it is composite with probability p = a constant < 1. The chance of error there can also be made exponentially small.
As you say, deterministic, or at least highly correlated, errors would dominate the chance that the proof was wrong. But that's true of human proofs too.
Large randomly generated primes are produced by a random algorithm like this, with a step that (when run on a composite number) shows that it is composite with probability p = a constant < 1. The chance of error there can also be made exponentially small.
As you say, deterministic, or at least highly correlated, errors would dominate the chance that the proof was wrong. But that's true of human proofs too.
> that's true of human proofs too.
I'm not sure that's right. The peer review process works well (e.g. [0]) precisely because human mathematicians are likely to make (at least somewhat) different mistakes from each other.
[0] https://en.wikipedia.org/w/index.php?title=Wiles%27s_proof_o...
I'm not sure that's right. The peer review process works well (e.g. [0]) precisely because human mathematicians are likely to make (at least somewhat) different mistakes from each other.
[0] https://en.wikipedia.org/w/index.php?title=Wiles%27s_proof_o...
Erdos did not live to see that (and it would have made no difference to his comment).
LOL. Not likely. The history of the proof is interesting. It was the first major proof that was done by computer. It reduced the set of graphs to about 2,000 and then brute forced it. Some refused to accept this was a "proof" in the traditional sense.
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.
Intuitive explanation about the proof? That might be tricky because it took a computer to prove it.
You 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.
There’s also a good popular overview of the history of the problem in the book “Four Colors Suffice” by Robin Wilson.
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
"Four Colors Suffice" by Robin Wilson
Long 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?
I 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.
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".
I know. Otherwise, I would have said some variation of “big if true.” Or, maybe I would have emailed him about it. :)
Looks like this is the paper:
COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE
https://arxiv.org/pdf/1905.02167.pdf
COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE
https://arxiv.org/pdf/1905.02167.pdf
This is linked in the first sentence of the article, FYI. (Though I guess it's easy to miss regardless…)
Link to abstract: https://arxiv.org/abs/1905.02167 .
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.
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.
> 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
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
The adjacency matrix of a graph normally has entries only 0 or 1.
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
Probably 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.
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.
yes: 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.
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?
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...
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.
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.)
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.)
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.
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.
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?
> 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?
I’m not sure exactly what situation you’re imagining. But as an illustrative example, if the central node has eight neighbors that are connected to each other in a cycle, the graph can be coloured with three colours like this:
2 -- 3 -- 2
| \ | / |
| \ | / |
3 -- 1 -- 3
| / | \ |
| / | \|
2 -- 3 -- 2"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
You could simply alternate colors around the node in that case:
#%#
%x%
#%#No, it doesn't have to share a color with a neighbor. The neighbors don't have to be neighbors to each other and can share colors.
The constraint is not on the number of neighbors directly. If there is just one node (say, A) with 4 neighbors (say B1, B2, B3, B4), we can color A red and B1, B2, B3, B4 blue. It only becomes a problem when all nodes are interconnected (i.e. the graph is complete). So, the result does imply that graphs which are not colorable with 4 colors are not planar. In particular, the complete graph (where all nodes of the graph are connected) with 4 nodes is not planar.
The complete graph with 4 nodes is planar, and obviously can be colored with only 4 colors -- that gives every node a unique color.
The complete graph with 5 nodes is what isn't planar. (That, and the complete bipartite graph with 3 nodes on each side.)
The complete graph with 5 nodes is what isn't planar. (That, and the complete bipartite graph with 3 nodes on each side.)
[deleted]
[deleted]
[deleted]
Think of a hypothetical earth:
1.The poles was each their own country with a color on the map
2. Every country stretch all the way from south to north
Every country in 2. then only need two colors. Because the “same” color can never meet in any point.
The fourth color comes into play if you have a new country that bridge the south (or north) and both of the countries in step 2. at the same time.
1.The poles was each their own country with a color on the map
2. Every country stretch all the way from south to north
Every country in 2. then only need two colors. Because the “same” color can never meet in any point.
The fourth color comes into play if you have a new country that bridge the south (or north) and both of the countries in step 2. at the same time.
[deleted]
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 :)
Could 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?
"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?
Four 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).
Thank 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).
An extra thank you for apparently creating a new account to assist me. (I think that's what the green username indicates, at least).
The 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.
Thank 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.
From 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?.. ;)
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?.. ;)
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.)