Tolerance orders of open and closed unit intervals (Q2314425)

In this paper the authors consider a special type of geometrically represented orders that stem from (a) tolerance orders, which are a slight generalization of interval orders where some overlap of the intervals are allowed, and (b) OC orders, which are interval orders in which each interval is either open or closed (that is, endpoints are either both excluded or both included.) The posets \(P = (X,\preceq)\) considered in this paper are those where each element \(x\in X\) is represented by a unit interval \(I_x\) with left, right and center points \(L(x), R(x)\) and \(c(x)\) respectively such that either (a) both endpoints \(L(x)\) and \(R(x)\) are included or both excluded, or (b) the center point \(c(x)\) is either included or excluded. This means that each interval \(I_x\) is of one of four possible types: \begin{itemize} \item[\(A\):] both endpoints and the center point are all included in the unit interval: \(\bullet\!\!-\!\!\bullet\!\!-\!\!\bullet\), \item[\(B\):] both endpoints and the center point are all excluded from the unit interval: \(\circ\!\!-\!\!\circ\!\!-\!\!\circ\), \item[\(C\):] the endpoints are included and the center point excluded from the unit interval: \(\bullet\!\!-\!\!\circ\!\!-\!\!\bullet\), \item[\(D\):] the endpoints are excluded and the center point included in the unit interval: \(\circ\!\!-\!\!\bullet\!\!-\!\!\circ\). \end{itemize} For a nonempty subset \(S\subseteq \{A,B,C,D\}\) an {\em \(S\)-order} is a poset \(P = (X,\preceq)\) such that each \(x\in X\) is represented by a unit interval \(I_x\) of type that belongs to \(S\) and such that \(x\prec y\) if and only if (i) \(R(x) < c(y)\), or (ii) \(R(x) = c(y)\) and at least one of \(R(x)\) and \(c(y)\) is excluded and at least one of \(L(y)\) and \(c(x)\) is excluded. Firstly, it is noted that whenever \(|S| = 1\), then an \(S\)-order is exactly the same as a unit interval order. Several classes of \(S\)-orders, when \(|S|\geq 2\), are characterized in this paper and examples that separate the unequal classes considered are given. For each \(S\subseteq \{A,B,C,D\}\), a polynomial-time algorithm that recognizes \(S\)-orders is given. This means that it provides a representation when one exists and a certificate that none exists otherwise.