Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/

by headalgorithm • 7 years ago

432 72 7 years ago

quantamagazine.org

FabHK2• 7 years ago

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.)

pmiller26• 7 years ago

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).

edjrage• 7 years ago

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.

klyrs2• 7 years ago

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.

FabHK2• 7 years ago

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).

gpvos• 7 years ago

Without the examples, I wouldn't have understood the article. And I did have some graph theory way back in university.

addicted• 7 years ago

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.

pmiller26• 7 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.... :)

avaku• 7 years ago

He commented (in the article) that he is delighted the resolution has been found and that "it can be explained in two sentences".

pmiller26• 7 years ago

I know. Otherwise, I would have said some variation of “big if true.” Or, maybe I would have emailed him about it. :)

C4stor• 7 years ago

The construction can be explained in two sentences, the argument proving this is a proper counter example not exactly I think !

_1• 7 years 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.

pmiller26• 7 years ago

He could probably do an entire course on just papers he wrote or co-wrote.

firstinstinct2• 7 years ago

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.

pmiller26• 7 years ago

What results and special cases did you work on?

firstinstinct2• 7 years ago

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.

hammock• 7 years ago

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.

b_tterc_p• 7 years ago

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.

jes5199• 7 years ago

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.

ky3• 7 years 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

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

glitcher• 7 years 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?

_blz22• 7 years ago

Intuitive explanation about the proof? That might be tricky because it took a computer to prove it.

intuitionist3• 7 years ago

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.

hawkice• 7 years ago

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".

jessriedel• 7 years ago

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.

achandlerwhite• 7 years ago

Numberphile covered it well: https://www.youtube.com/watch?v=NgbK43jB4rQ

It's also got a lot of videos on other cool math stuff.

jnordwick• 7 years ago

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.

avip2• 7 years ago

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

pfdietz4• 7 years ago

The proof has been formalized and verified in the Coq theorem proving system, which is good evidence it is correct.

kccqzy• 7 years ago

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.

emptybits• 7 years ago

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

_blz22• 7 years ago

Looks like this is the paper:

COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE

https://arxiv.org/pdf/1905.02167.pdf

svat• 7 years ago

This is linked in the first sentence of the article, FYI. (Though I guess it's easy to miss regardless…)

JadeNB• 7 years ago

Link to abstract: https://arxiv.org/abs/1905.02167 .

2bitencryption2• 7 years ago

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?

dnadler• 7 years ago

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.

2bitencryption2• 7 years ago

it took me a moment, but now it seems obvious. Thanks :)

kfichter• 7 years ago

You could simply alternate colors around the node in that case:

  #%#
  %x%
  #%#

andrelaszlo• 7 years 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

kryptiskt• 7 years ago

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.

robinhouston• 7 years ago

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

punnerud• 7 years ago

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.

meuk• 7 years ago

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.

thaumasiotes• 7 years ago

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.)

MrXOR• 7 years ago

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!

dylanfw3• 7 years ago

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?

karmakaze• 7 years ago

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.

dylanfw3• 7 years ago

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.

philipfweiss• 7 years ago

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).

dylanfw3• 7 years ago

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).

Cogito3• 7 years ago

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?

OscarCunningham• 7 years ago

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...

Cogito3• 7 years ago

Thanks, that's a really great example. It definitely feels non trivial to come up with an example.

intuitionist3• 7 years ago

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.)

Cogito3• 7 years ago

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.

thesz• 7 years ago

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?.. ;)

Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

Related Stories