Publications > Artigos em Revistas Internacionais

On the homomorphism order of labeled posets

Kwuida, Léonard; Lehtonen, Erkko

Order, 28 (2011), 251-265
http://dx.doi.org/10.1007/s11083-010-9169-x

Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. We give a representation of directed graphs by k-posets; this provides a new proof of the universality of the homomorphism order of k-posets. This universal order is a distributive lattice. We investigate some other properties, namely the infinite distributivity, the computation of infinite suprema and infima, and the complexity of certain decision problems involving the homomorphism order of k-posets. Sublattices are also examined.