Mathematician Disproves Hedetniemi’s Graph Theory Conjecture
quantamagazine.org
quantamagazine.org
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.)
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.
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.
"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!
> 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?
There’s also a good popular overview of the history of the problem in the book “Four Colors Suffice” by Robin Wilson.
It's also got a lot of videos on other cool math stuff.
P. Erdos
A proof that requires a computer to understand it is not helpful for these goals. The proof's veracity is not in question.
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.
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.
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?
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.
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.
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...
"Four Colors Suffice" by Robin Wilson
and apparently humble, too. I had one undergrad and one graduate class from him and didn't know about this.
COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE
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.
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.
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?
https://standardwisdom.com/softwarejournal/2012/07/a-graph-t...
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.)
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.
> 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?
#%#
%x%
#%# 2 -- 3 -- 2
| \ | / |
| \ | / |
3 -- 1 -- 3
| / | \ |
| / | \|
2 -- 3 -- 21.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.
The complete graph with 5 nodes is what isn't planar. (That, and the complete bipartite graph with 3 nodes on each side.)
"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?
An extra thank you for apparently creating a new account to assist me. (I think that's what the green username indicates, at least).
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?.. ;)