On locally presented posets (Q913830)

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 encoding of a subclass of the class of planar directed acyclic graphs is introduced.