Split semiorders

DOI10.1016/S0012-365X(98)00170-8MaRDI QIDQ1296976zbMATH OpenOpenAlexFDO

Authors Peter Fishburn, William T. Trotter

Publication date 3 August 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(98)00170-8

bipartite posets distinguishing representations finite posets poset dimension split interval orders split semiorders tolerance orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Review text

Let \({\mathcal P}\) be the class of finite posets. Various subclasses of \({\mathcal P}\) generalizing the class of linear orders (weak orders, semiorders, interval orders, tolerance orders, etc.) have been studied recently. The authors deal mainly with the classes of split semiorders and split interval orders. A poset \(P=(X,\prec)\) is called a split semiorder if there are maps \(a,f:X\to R\) with \(a(x)\leq f(x)= a(x)+1\) for every \(x\in X\) such that \(x\prec y\) iff \(f(x)<a(y)\) and \(a(x)+1 <f(y)\). A split interval order is defined analogously starting from the notion of an interval order. In the paper the mentioned classes are compared with other important classes of posets and this comparison is completed by describing the triples of the maximun values of Idim, Sdim and dim for each class. Further it is proved that split semiorders and split interval orders have distinguishing representations. Minimally forbidden posets for the classes of posets in question are described there too. Finally, bipartite posets distinguishing classes of posets are discussed.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Split semiorders

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