Antichains in the homomorphism order of graphs
Dwight Duffus, Péter L. Erdős, Jaroslav Nešetřil, Lajos Soukup · Czech digital mathematics library · 2007
Denote by G and D, respectively, the the homomorphism poset of the finite undirected and directed graphs, respectively. A maximal antichain A in a poset P splits if A has a partition (B, C) such that for each p ∈ P either b ≤P p for some b ∈ B or p ≤p c for some c ∈ C. We construct both splitting and non-splitting infinite maximal antichains in G and in D. A point y ∈ P is a cut point in a poset P if and only if there is x <p<P y < z such that [x, z] = [x, y] ∪ [y, z]. We show if G ∈ D contains any directed circle, then G can not be a cut point in D. 1