Boolean dimension and tree-width (Q2658384)

The dimension of a partially ordered set (poset) \((P,\prec)\), denoted dim\((P)\), is the smallest number of linear extensions (i.e. total orders which agree with the partial order where it is defined) whose intersection is the poset. Posets with small dimension tend to be tractable in various ways as dimension is some kind of measure of the complexity of the poset. \textit{J. Nešetřil} and \textit{P. Pudlák} [in: Irregularities of partitions. Papers from the meeting held at Fertod, Hungary, from July 7th through 10th, 1986. Berlin etc.: Springer-Verlag. 137--140 (1989; ZBL 0683.06003)] introduced a variant called Boolean dimension, which is the smallest number of linear orders on the underlying set \(P\) whose intersection is the partial order. (The difference is that the orders need not be linear extensions of the underlying poset). Clearly bdim\((P)\leq \) dim\((P)\). Whereas the dimension can be linear in the number of vertices \(n=\vert P\vert\) for a finite \(P\) e.g. for the so-called ``standard examples'', it is known that bdim\((P)=O(\log(n))\) from Nešetřil and Pudl'{a}k's paper [loc. cit.]. \par The cover graph of a poset \(P\) has the same vertices as \(P\) and an edge from \(x\) to \(y\) if \(x\prec y\) or \(y\prec x\) and there is no element \(z\) such that \(x\prec z\prec y\) or \(y\prec z\prec x\). The main result of the paper under review is that if the cover graph of a poset has bounded tree-width, then the Boolean dimension is bounded. The authors also present some interconnected open problems in the area.