On the homomorphism order of labeled posets

Abstract

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.

14 pages

Cited by in corpus (3)

• Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
• On the isomorphism problem of concept algebras
• Universality of intervals of line graph order