Caltech Home > PMA Home > Master Calendar > Logic Seminar
Tuesday, August 20, 2019
2:00 PM - 3:00 PM
Linde Hall 255

# Logic Seminar

Refutation of Hedetniemi's conjecture
Forte Shinko, Mathematics Department, Caltech,

Given two graphs G and H, a trivial upper bound for the chromatic number of G\times H is the chromatic number of G (and also the chromatic number of H). Hedetniemi's conjecture, dating back to 1966, states that this upper bound is always an equality, that is to say that \chi(G\times H) = \min(\chi(G),\chi(H)) for any finite simple graphs G and H. Hajnal showed in 1985 that the generalization to infinite graphs is false, but the conjecture for finite graphs, and even the generalization to Borel chromatic numbers of analytic graphs on Polish spaces, remained unresolved. Recently, Shitov has shown that Hedetniemi's conjecture is false, using the exponential graphs of El-Zahar and Sauer. We will present an outline of this proof.