Xuding Zhu: Hedetniemi's conjecture and the Poljak-Rödl function

Description of video

Date: 9/11/20
Speaker :Zhu Xuding

Abstract: Hedetniemi conjectured in 1966 that χ(G×H)=min{χ(G),χ(H)} for all graphs G,H. This conjecture received a lot of attention in the past half century and was eventually refuted by Shitov in 2019. The Poljak-Rödl function is defined as f(n)=min{χ(G×H):χ(G)=χ(H)=n}. It is obvious that f(n)n for all n, and Hedetniemi’s conjecture is equivalent to say that f(n)=n for all integer n. Now we know that f(n)<n for large n. However, we do not know how small f(n) can be. In this talk, we will present new counterexamples to Hedetniemi's conjecture. We show that f(n)(12+o(1))n and survey some other work related to Hedetniemi’s conjecture.