Tolerance orders of open and closed unit intervals

Abstract: In this paper we combine ideas from tolerance orders with recent work on OC interval orders. We consider representations of posets by unit intervals

I_{v}

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

I_{v}

of type belonging to

S

, and

x p r e c 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 s u b s e t e q 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.

Review text

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Tolerance orders of open and closed unit intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2314425)