Two days ago Nati Linial sent me an email entitled “A sensation in the morning news”. The link was to a new arXived paper by Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.
Hedetniemi’s 1966 conjecture asserts that if and are two graphs, then the chromatic number of their tensor product equals the minimum of their individual chromatic numbers. Here, the vertex set of is the Cartesian product of and and two vertices and are adjacent if is adjacent to and is adjacent to . Every coloring of induces a coloring of , and so is every coloring of . Therefore, . Hedetniemi conjectured that equality always hold and this is now refuted by by Yaroslav Shitov.
The example and the entire proof are quite short (the entire paper is less than 3 pages; It is a bit densely-written).
To tell you what the construction is, I need two important definitions. The first is the notion of the exponential graph .
The exponential graph arose in the study of Hedetniemi’s conjecture in a 1985 paper by El-Zahar and Sauer. The vertices of are all maps from to . Two maps are adjacent if whenever are adjacent vertices of then . El-Zahar and Sauer showed that importance of the case that is a graph and is an exponential graph of for Hedetniemi’s conjecture. (The entire conjecture reduces to this case.) It is thus crucial to study coloring of exponential graphs which is the subject of the three claims of Section 1 of Shitov’s paper.
The second definition is another important notion of product of graphs: The strong product G ⊠ H of two graphs and . The set of vertices is again the Cartesian product of the two sets of vertices. This time, and are adjacent in G ⊠ H if either
(a) is adjacent to and is adjacent to
(b) is adjacent to and or and is adjacent to
(The edges of condition (a) are the edges of the tensor product of the two graphs and the edges of condition (b) are the edges of the Cartesian product of the two graphs.)
For Shitov’s counterexample given in Section 2 of his paper, is the strong product of a graph with girth at least 10 and fractional chromatic number at least 4.1 with a large clique of size . The second graph is the exponential graph . Put . Shitov shows that when is sufficiently large then the chromatic number of both is , but the chromatic number of their tensor product is smaller than .
(Have a look also at Yaroslav’s other arXived papers! )
Update: In v2 it is pointed out that it is enough to take the girth at least 6 and the fractional chromatic number at least 3.1.
Finite and infinite combinatorics
Let me make one more remark. (See the Wikipedea article.) The infinite version of Hedetniemi’s conjecture was known to be false. Hajnal (1985) gave an example of two infinite graphs, each requiring an uncountable number of colors, such that their product can be colored with only countably many colors. Rinot (2013) proved that in the constructible universe, for every infinite cardinal , there exist a pair of graphs of chromatic number greater than , such that their product can still be colored with only countably many colors. (Here is the paper.) Is there a relation between the finite case and the infinite case? (Both theories are quite exciting but direct connections are rare. A rare statement where the same proof applies for the finite and infinite case is the inequality .
Here is a link to a survey article by Claude Tardif, (2008), “Hedetniemi’s conjecture, 40 years later” .
A few more thing worth knowing:
1) The weak version of the conjecture that asserts that If , then where tends to infinity with is still open.
2) Xuding Zhu proved in 2011 that the fractional version of the conjecture is correct,
3) The directed version of the conjecture was known to be false (Poljak and Rodl, 1981).
4) The conjecture is part of a rich and beautiful theory of graph homomorphisms (and the category of graphs) that I hope to come back to in another post.
Belated links on Yaroslav Shitov’s disproof of Hedetniemi’s conjecture
(Added Dec 23, 2019. ) Here are links to strengthenings of Shitov’s result by Claude Tardif and Xuding Zhu and by by Xiaoyu He and Yuval Wigderson. And here is a lovely Quanta Magazine article by Erica Klarreich about it, ending with a quote by Noga Alon: “Sometimes, the reason that a conjecture is very hard to prove is simply that it is false.” Here is a numberphile video by Erica Klarreich.
Have you or someone you know verified the proof ? Personally, I got stuck at Claim 3. In particular, why do most (i.e. Omega(c^n)) of the V_b’s have a non-empty intersection ? (I could not follow the reasoning for this claim.)
Let me ask something even easier: Why do most pairs V_a and V_b (for two color classes a and b) have a common vertex ?
Nevermind my above comment. I think Claim 3 makes sense.
Thanks Anon. By now several people verified the proof. I added some more information on The Weak Hedetniemi Conjecture and other things at the end of the post. See also Reddit discussion.
Pingback: The Hedetniemi’s conjecture has been disproven - Nevin Manimala's Blog
Regarding the connection between the finite and infinite cases, I think you can show by appealing to the DeBruijn-Erdos theorem that the weak Hedetniemi conjecture is equivalent to the assertion that there are no graphs with infinite chromatic number such that the chromatic number of is finite.
I don’t think the weak Hedetniemi conjecture follows immediately from the assertion about infinite chromatic number. Hajnal (1985) proved that if has infinite chromatic number and has finite chromatic number , then has chromatic number . He really proved that for natural numbers , if has chromatic number and has vertices and chromatic number , then has chromatic number . I think this latter fact (or something similar) is the finite statement that follows from the theorem you propose.
A comment from Assaf Rinot:
I do not think there is a logical implication here between the
infinitary problem and the finitary. I also do not wish to shift the
discussion from Shitov’s remarkable achievement into peripheral
matters. But in case there’s anyone who might be interested in
exploring the finite vs. infinite matter, I’ll mention that your
description of Shitov’s counterexample made me realize that something
like the exponential graphs appeared in my infinitary counterexample
to the weak conjecture.
Specifically, for the infinitary counterexample, I first construct two
graphs and of very large (uncountable, etc’)
chromatic number, yet, all of their small subgraphs (indeed, initial
segments) are merely countably chromatic. I then derive two graphs
and , letting consist (roughly) of good
colorings of small subgraphs of , and setting that two good
colorings are -adjacent if one extends the other and their
corresponding domains are -related. It is then straight-forward
to verify that tensor product has a small
The heart of the matter is to ensure that each of the components is of
large chromatic number, and this is done by utilizing the
fine-structural nature of Godel’s constructible universe together with
some forcing insights (the graphs live in Godel’s model, but in order
to compute their chromatic number we actually pass to two forcing
extensions – one for each graph).
To the interested reader: have a look at Slide 24 (PDF-page 55) onward
of http://www.assafrinot.com/files/rinot_esi2013.pdf and see whether
the approach described there has a finitary counterpart.
Dear Prof. Kalai,
Let me thank you for verifying my counterexample and advertising it with your blog post! Can you please explain the title? What does the sans-ation wordplay mean?
With best regards,
Congratulations for the result!
The title is an embarrassing typo, should be “sensation in the morning news” now corrected.
best regards, Gil
Pingback: Shtetl-Optimized » Blog Archive » Quanta of
Dear Prof. Kalai,
I don’t quite understand the definition of the exponential graph. In the definition of adjacency, it is not clear to me if the definition is symmetric wrt. \phi and \psi.
Pingback: A young Russian denies a conjecture with more than half a century of life | Science | Spain's News
Pingback: Un matemático ruso desmiente una conjetura con más de medio siglo de vida - BoliviaMaya
Pingback: La optimización de tiempos ¿replanteada por Shitov? - Consultorio Cardano
Pingback: Amazing: Hao Huang Proved the Sensitivity Conjecture! | Combinatorics and more
Pingback: Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics | Combinatorics and more
Pingback: Graph Products | Gödel's Lost Letter and P=NP
Pingback: Just when you think it’s over | Igor Pak's blog
Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more