2017/07/25 by Alan Shuchat, Shuchat, Alan, Randy Shull +3
Computer Science · #05C75 #06A06 #Advanced Algebra and Logic #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1707.08099
openalex publication_date 2017/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we combine ideas from tolerance orders with recent work on OC interval orders. We consider representations of posets by unit intervals Iv in which the interval endpoints (L(v) and R(v)) may be open or closed as well as the center point (c(v)). This yields four types of intervals: A (endpoints and center points closed), B (endpoints and center points open), C (endpoints closed, center points open), and D (endpoints open, center points closed). For any non-empty subset S of \A,B,C,D\, we define an S-order as a poset P that has a representation as follows: each element v of P is assigned a unit interval Iv of type belonging to S, and x \prec y if and only if either (i) R(x) < c(y) or (ii) R(x) = c(y) and at least one of R(x), c(y) is open and at least one of L(y), c(x) is open. We characterize several of the classes of S-orders and provide separating examples between unequal classes. In addition, for each S ⊆ \A,B,C,D\ we present a polynomial-time algorithm that recognizes S-orders, providing a representation when one exists and otherwise providing a certificate showing it is not an S-order.