A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.

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 G and H are two graphs, then the chromatic number of their tensor product G \times H equals the minimum of their individual chromatic numbers.  Here, the vertex set of G \times H is the Cartesian product of V(G) and V(H) and two vertices (g_1,h_1) and (g_2,h_2) are adjacent if g_1 is adjacent to g_2 and  h_1 is adjacent to h_2. Every coloring of G induces a coloring  of G \times H, and so is every coloring of H.  Therefore, \chi (G \times H) \le \min (\chi (G), \chi (H)). 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).

Yaroslav Shitov 

To tell you what the construction is, I need two important definitions.  The first  is the notion of the exponential graph {\cal E}_c(H).

The exponential graph  {\cal E}_c(H) arose in the study of Hedetniemi’s conjecture in a 1985 paper by El-Zahar and Sauer. The vertices of {\cal E}_c(H) are all maps from V(H) to \{1,2,\dots,c\}. Two maps \phi, \psi are adjacent if whenever v,u are adjacent vertices of H then \phi(u) \ne \psi (v)El-Zahar and Sauer showed that importance of the case  that H is a graph and G is an exponential graph of H 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 H and G. The set of vertices is again the Cartesian product of the two sets of vertices. This time,  (g_1,h_1) and (g_2,h_2) are adjacent in G ⊠ H if either

(a) g_1 is adjacent to g_2 and  h_1 is adjacent to h_2


(b) g_1 is adjacent to g_2 and  h_1 = h_2 or g_1 =g_2 and  h_1 is adjacent to h_2

(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, H is the strong product of a graph L with girth at least 10 and fractional chromatic number at least 4.1 with a large clique of size q. The second graph G is the exponential graph {\cal E}_c(H). Put c =\lceil 4.1q \rceil.  Shitov shows that when q is sufficiently large then  the chromatic number of both H,G is c,  but the chromatic number of their tensor product is smaller than c.

(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 2^n>n.

More information

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 \chi (G)= \chi (H))=n, then \chi (G \times H) \ge f(n) where f(n) tends to infinity with n 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.

This entry was posted in Combinatorics, Open problems, Updates and tagged , . Bookmark the permalink.

19 Responses to A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.

  1. ANon says:

    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 ?

  2. Pingback: The Hedetniemi’s conjecture has been disproven - Nevin Manimala's Blog

  3. dsp says:

    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 G, H with infinite chromatic number such that the chromatic number of G \times H is finite.

    • Anon80 says:

      I don’t think the weak Hedetniemi conjecture follows immediately from the assertion about infinite chromatic number. Hajnal (1985) proved that if G has infinite chromatic number and H has finite chromatic number n, then G\times H has chromatic number n. He really proved that for natural numbers n,k, if G has chromatic number k^n and H has n vertices and chromatic number k, then G\times H has chromatic number k. I think this latter fact (or something similar) is the finite statement that follows from the theorem you propose.

  4. Gil Kalai says:

    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 (G_0,E_0) and (G_1,E_1) 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
    (V_0,F_0) and (V_1,F_1), letting V_i consist (roughly) of good
    colorings of small subgraphs of G_{i-1}, and setting that two good
    colorings are F_i-adjacent if one extends the other and their
    corresponding domains are E_i-related. It is then straight-forward
    to verify that (V_0,F_0) tensor product (V_1,F_1) has a small
    chromatic number.

    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.

  5. yaroslav shitov says:

    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,

  6. Gil Kalai says:

    Dear Yaroslav,
    Congratulations for the result!
    The title is an embarrassing typo, should be “sensation in the morning news” now corrected.
    best regards, Gil

  7. Pingback: Shtetl-Optimized » Blog Archive » Quanta of

  8. fanzheng1729 says:

    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.

  9. Pingback: A young Russian denies a conjecture with more than half a century of life | Science | Spain's News

  10. Pingback: Un matemático ruso desmiente una conjetura con más de medio siglo de vida - BoliviaMaya

  11. Pingback: La optimización de tiempos ¿replanteada por Shitov? - Consultorio Cardano

  12. Pingback: Amazing: Hao Huang Proved the Sensitivity Conjecture! | Combinatorics and more

  13. Pingback: Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics | Combinatorics and more

  14. Pingback: Graph Products | Gödel's Lost Letter and P=NP

  15. Pingback: Just when you think it’s over | Igor Pak's blog

  16. Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s