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 . (mistake corrected.) 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).

** Yaroslav Shitov **

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

OR

(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! )

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

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

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

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.

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

Dear Yaroslav,

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