D. Duffus, P.L. Erd{\H o}s, J. Ne\v set\v ril, L. Soukup
Antichains in the homomorphism order of graphs

Comment.Math.Univ.Carolin. 48,4 (2007) 571-583.

Abstract:Let $\Bbb G$ and $\Bbb D$, respectively, denote the partially ordered sets of homomorphism classes of finite undirected and directed graphs, respectively, both ordered by the homomorphism relation. Order theoretic properties of both have been studied extensively, and have interesting connections to familiar graph properties and parameters. In particular, the notion of a duality is closely related to the idea of splitting a maximal antichain. We construct both splitting and non-splitting infinite maximal antichains in $\Bbb G$ and in $\Bbb D$. The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs.

Keywords: partially ordered set, homomorphism order, duality, antichain, splitting property
AMS Subject Classification: Primary 06A07; Secondary 05C99