Caltech Logo

Logic Seminar

Tuesday, August 20, 2019
2:00pm to 3:00pm
Add to Cal
Linde Hall 255
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.