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.

For more information, please contact Mathematics Department by phone at 626-395-4335 or by email at mathinfo@caltech.edu.