Lattices arising in categorial investigations of Hedetniemi's conjecture

✍ Scribed by Dwight Duffus; Norbert Sauer

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 844 KB
• Volume: 152
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00298-w

✦ Synopsis

We discuss Hedetniemi's conjecture in the context of categories of relational structures under homomorphisms. In this language Hedetniemi's conjecture says that if there are no homomorphisms from the graphs G and H to the complete graph on n vertices then there is no homomorphism from G x H to the complete graph. If an object in some category has just this property then it is called multiplicative. The skeleton of a category of relational structures under homomorphisms forms a distributive lattice which has for each of the objects K of the category a pseudocomplementation. The image of the distributive lattice under such a pseudocomplementation is a Boolean lattice with the same meet as the distributive lattice and the structure K is multiplicative if and only if this Boolean lattice consists of at most two elements. We will exploit those general ideas to gain some understanding of the situation in the case of graphs and solve completely the Hedetniemi-type problem in the case of relational structures over a unary language.