Predavatelj: Claude Tardif – University of Regina, Kanada
The best description of homomorphism duality is the title "For every answer there are two questions" of a paper by Fink and Garcia. Graph colouring is an example of a tough homomorphism problem, and in a sense, what seems to be lacking is a second question. Hovewer, some homomorphisms problems are dualizable (that is, admit a second question) and my joint work with Jaroslav Nesetril allowed us to characterise such dualities. The subject is related to Welzl’s density theorem.
