Interval Orders and Interval Graphs: A Study of Partially Ordered Sets

₁y a₁ a₂ agreeing interval order antichain Assume henceforth B₁ B₂ binary relation buried subgraph C₁ C₂ chain chapter characteristic matrix closed real representation comparability graph components contradiction Corollary countable defined definition denote easily seen eight-point semiorder equivalence class equivalence relation Figure finite interval order follows Given Hasse diagram Hence holds hypotheses implies indifference graph inequalities integer intersect interval graph irreflexive isomorphic k-point left endpoint linear extension linear order linearly ordered set main diagonal maximal cliques Moreover nine-point semiorder nonempty number of lengths order dense order that agrees orders and interval P₁ P₂ pair partial order partial semiorder poset proof of Theorem prove Rado's theorem reflexive graph related set restriction right endpoint satisfies simplicial points strict betweenness relation subset Suppose symmetric complement transitive weak order x₁ Y₁ Y₂