Bounded discrete representations of interval orders (Q686255)

Given a finite interval order \((A,>)\) and \(\alpha,\beta: A\to\mathbb{N}\) non- negative integer constraints, an \([\alpha,\beta]\) bounded discrete representation of \((A,>)\) is a closed interval representation \({\mathcal J}: A\to \{[\ell,r]\mid \ell,r\in\mathbb{Z}\}\) so that \({\mathcal J}(a_ i)={\mathcal J}(i)= [\ell_ i,r_ i]\) with (a) \(j>j \iff \ell_ i> r_ j\) and (b) \(\alpha(i)\geq r_ i-\ell_ i\geq \beta(i)\) for all \(i\in A\), with \({\mathcal D}[\alpha,\beta]\) denoting the collection of all finite interval orders permitting bounded discrete representations while \({\mathcal F}[\alpha,\beta]\) consists of those interval orders not in \({\mathcal D}[\alpha,\beta]\) having the property that all proper suborders \(A'\) of \(A\) are in \({\mathcal D}[\alpha,\beta]\). In this very useful paper, the author obtains a variety of interesting results by studying a directed graph \(D(A,>,\alpha,\beta)\) and its flow properties via the vertex-incidence matrix \(M\) of this graph and its relationships to these properties in terms of associated linear algebra, as expressed in Farkas' Lemma for example. The graph \(D(A,>,\alpha,\beta)\) is bipartite with vertices \(L\cup R=\{\ell_ 1, \dots,\ell_{| A|}\}\cup \{r_ 1,\dots, r_{| A|}\}\) and arcs \(U\cup V\cup W\cup Z\) with lengths (weights) \(U=\{(\ell_ i,r_ i)\): \(i=1,\dots,| A|\}\) lengths \(\alpha(i)\), \(V=\{(r_ i,\ell_ i)\}\) lengths \(-\beta(i)\), \(W=\{(\ell_ i,r_ j)\): \(i>j\}\) lengths \(-1\), \(Z=\{(r_ j,\ell_ i)\): \(i\) and \(j\) equal or incomparable\} lengths 0. A key idea involved is that of a negative cycle, i.e., a cycle of negative length in that \((A,>)\in {\mathcal D}[\alpha,\beta]\) iff \(D(A,\geq,\alpha,\beta)\) contains no negative cycles. Based on this approach the author is able to provide a polynomial time decision algorithm for membership in \({\mathcal D}[\alpha,\beta]\) as well as further properties of \({\mathcal F}[\alpha,0]\) (finite) and \({\mathcal F}[\alpha,1]\) (infinite if \(\alpha\geq 2)\). In the latter cases properties of negative cycles in graphs \(D(A,>,\alpha,0)\) and \(D(A,>,\alpha,\beta)\) are important.