On locally presented posets
type: Item
instance of: scholarly article
title: On locally presented posets
zbMATH Open document ID: 0701.06003
DOI: 10.1016/0304-3975(90)90125-2
author: Giorgio Gambosi
author: Maurizio Talamo
author: J. Nešetřil
published in: Theoretical Computer Science
publication date: 1990-01-01T00:00:00Z
review text: Several interesting concepts and useful conclusions are presented in this paper marred here and there by deletions or misprints that present possible obstacles to readers not experienced with the subject. Given a poset P, with \(| P| =n\), the number of vertices, a labeling L is an (order)-homomorphism L: \(P\to [1,...,n]\) with the natural order, whose induced order on P is an extension of the original order. Thus if \(U_ 1\leq U_ 2\) (in P), then \(U_ 1\leq U_ 2\) (in L) as well. Suppose \({\mathcal F}\) is a boolean formula defined on a set \(\{X_ 1,...,X_ t\}\) of boolean variables. Suppose furthermore that there exist t labelings \(<L_ 1,...,L_ t>\) on P such that \(U_ 1\leq U_ 2\) (in P) iff \({\mathcal F}(X_ 1,...,X_ t)=1\), where \(X_ i=1\) iff \(U_ 1\leq U_ 2\) (in \(L_ i)\). Then P is \({\mathcal F}\)-representable and the labelings \(<L_ 1,...,L_ t>\), plus the boolean formula \({\mathcal F}\) form a local presentation of P, with P being locally presented. The point of this exercise is that if \({\mathcal F}=X_ 1\wedge X_ 2\wedge...\wedge X_ t\), then the local presentation obtained from \({\mathcal F}\) plus the requirement that the \(L_ i\) be linear estensions of P, leads to the observation that for minimal t, one has computed dim(P). Thus, if \({\mathcal F}\) is restricted to be an acyclic formula while the \(L_ i\) are not restricted otherwise, the resulting dimension, obtained by letting t be minimal, denoted by \(\dim_ B(P)\), the boolean dimension, is a lower bound for dim(P), which may or may not equal dim(P). It is shown that if \(n=1\), 2 or 3 these are equal, while if \(n\geq 4\), then there exists a poset \(P_ n\) such that \(\dim_ B(P_ n)=4\leq \dim (P_ n)=n\). The role of the system \(\{\) \({\mathcal F}\); \(<L_ 1,...,L_ t>\}\) in encoding P and of \(\dim_ B(P)\) in determining the efficiency of encoding, as well as determining most efficient encodings is of theoretical interest and importance. As a special application an efficient encodin…
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 06E99
zbMATH DE Number: 4148154
zbMATH Keywords: dimensions
zbMATH Keywords: labeling
zbMATH Keywords: boolean formula
zbMATH Keywords: local presentation
zbMATH Keywords: boolean dimension
zbMATH Keywords: efficient encodings
zbMATH Keywords: planar directed acyclic graphs
reviewed by: J. Neggers
MaRDI profile type: Publication
full work available at URL: 0304-3975(90)90125-2
OpenAlex ID: W2051113106
cites work: Chordality properties on graphs and minimal conceptual connections in semantic data models
cites work: Q3767386
cites work: Q3783593
cites work: Q4732500
cites work: Q3344241
cites work: Q3321495
cites work: The dimension of planar posets
description: scientific article; zbMATH DE number 4148154