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

Posted on May 10, 2019 by Gil Kalai

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 $\kappa$ , there exist a pair of graphs of chromatic number greater than $\kappa$ , 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 Hedetniemi's conjecture, Yaroslav Shitov. Bookmark the permalink.

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

ANon says:

May 10, 2019 at 11:46 pm

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 ?

Reply
- ANon says:
  
  May 11, 2019 at 2:25 am
  
  Nevermind my above comment. I think Claim 3 makes sense.
  
  Reply
  - Gil Kalai says:
    
    May 11, 2019 at 3:11 pm
    
    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
dsp says:

May 11, 2019 at 6:56 pm

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.

Reply
- Anon80 says:
  
  May 12, 2019 at 5:19 am
  
  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.
  
  Reply
Gil Kalai says:

May 11, 2019 at 7:39 pm

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.

Reply
yaroslav shitov says:

May 12, 2019 at 7:37 pm

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,
Yaroslav

Reply
Gil Kalai says:

May 12, 2019 at 7:52 pm

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

Reply
Pingback: Shtetl-Optimized » Blog Archive » Quanta of
fanzheng1729 says:

June 23, 2019 at 11:02 pm

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.

Reply
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

	Questions and Concer… on Inaugural address at the Hunga…
	Questions and Concer… on The Argument Against Quantum C…
	Questions and Concer… on Physics Related News: Israel J…
	Questions and Concer… on The Google Supremacy Experimen…
	Questions and Concer… on Remarkable: “Limitations…
	Questions and Concer… on Ordinary computers can beat Go…
	Questions and Concer… on Amazing: Feng Pan and Pan Zhan…
	Gil Kalai on An Aperiodic Monotile
	Gil Kalai on Physics Related News: Israel J…
	Mostafa Touny on Physics Related News: Israel J…
	Gil Kalai on Stand Clear of The Closing Doo…
	Gil Kalai on Test your intuition 52: Can yo…