Partial orders and their convex subsets
type: Item
instance of: scholarly article
title: Partial orders and their convex subsets
zbMATH Open document ID: 0880.06001
DOI: 10.1016/S0012-365X(96)00197-5
author: Haiko Müller
author: Jean-Xavier Rampon
published in: Discrete Mathematics
publication date: 1997-06-10T00:00:00Z
review text: Let \(P=(P,<)\) and \(Q=(Q,<)\) be (partially) ordered sets. Then \(P\) is called to be representable by a visibility relation of convex connected subsets of \(Q\) if there exists a mapping \(\varphi\) of \(P\) into the set of convex connected subsets of \(Q\) such that, for any \(x, y\in P\), \(x<y\) if and only if (i) \(\varphi(x) \cap\varphi (y)= \emptyset\), and (ii) there exist elements \(e_x\in \varphi(x)\) and \(e_y\in \varphi(y)\) with \(e_x<e_y\). If this is the case then \(Q\) is a host order for \(P\). The authors study and characterize some classes of ordered sets which can have host orders belonging to given classes of ordered sets. Especially, they describe the classes of ordered sets with in-tree and grid order as hosts. Note that the paper provides generalizations of interval orders since they are exactly those orders representable by visibility in total orders. This method is more general than another generalization of interval orders used, e.g., by \textit{J. Mitas} [Discrete Math. 144, 75-95 (1995; Zbl 0837.06001)].
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 1019119
zbMATH Keywords: convex subset
zbMATH Keywords: visibility relation
zbMATH Keywords: host order
zbMATH Keywords: grid order
zbMATH Keywords: generalizations of interval orders
reviewed by: Jiří Rachůnek
MaRDI profile type: Publication
cites work: The convexity lattice of a poset
cites work: Q4525258
cites work: Interval orders based on weak orders
cites work: The communication complexity of interval orders
cites work: Q3138973
cites work: Interval orders based on arbitrary ordered sets
cites work: Q4004146
full work available at URL: s0012-365x(96)00197-5
OpenAlex ID: W2016553430
description: scientific article; zbMATH DE number 1019119