THE PARTIAL ORDER OF GRAPHS AND HOMOMORPHISMS
Pavol Hell, Jaroslav Nešetřil · Oxford University Press eBooks · 2004
This chapter considers the order homomorphisms induce on the set of all cores; this order is rich enough to represent all countable partial orders. Antichains in the homomorphism order are discussed, which are collections of incomparable graphs (graphs without homomorphisms between any two of them). Of particular interest are finite maximal antichains, and their structure turns out to be surprisingly revealing. Graphs only have trivial finite maximal antichains, while digraphs have many such antichains of all possible sizes, arising from duality relationships. This chapter also contains the (probabilistic) proof of the Sparse Incomparability Lemma, of the fact that asymptotically almost all graphs on $n$ vertices are cores, and of the fact that the number of incomparable graphs on $n$ vertices differs little (asymptotically) from the total number of non-isomorphic graphs on $n$ vertices. The density of the homomorphism order is related to duality, revealing an unexpected connection between these two seemingly unrelated concepts. Finally, it is shown that one can gain interesting insights into many traditional graph topics, such as Hadwiger’s conjecture, when interpreting them as statements about the homomorphism order.