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.