Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 10, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jan Foniok (Queen's University)
Theorem (Geller, Stahl): Let G be a graph. Then the lexicographic product G[K2] is n-colourable if and only if G admits a homomorphism to the Kneser graph K(n,2).
Theorem (El-Zahar, Sauer): For two graphs G and H, the categorial product G × H is n-colourable if and only if G admits a homomorphism to the exponential graph KnH.
What do these two theorems have in common? Each is an example of the same phenomenon, known in category theory as adjoint functors. I will explain what they are and show some other applications, such as a circular version of the Gallai–Roy (–Hasse–Vitaver) Theorem.
Automatic MiSe System Software Version 1.4803M | admin login